「雅礼集训 2017 Day8」价
内存限制: 512 MiB时间限制: 1000 ms输入文件: z.in输出文件: z.out
【分析】
蛤？一开始看错题了，但是也没有改，因为不会做。
一开始以为是并集全等，其实只是集合内元素个数相等。
如果是一开始的题意的话，就是选了什么药材就要选什么药，明显的一个最大权闭合子图【于是我真的就这样打了，加上暴力还搞了很多分
数量一样的话，男神有一个方法就是放大点权，普通选法的话左边比右边少，所以药的点权+INF，药材的点权-INF，然后做最大权闭合子图【我对此只能膜膜膜
然后题目有一个条件就是要完美匹配。
正解是先做一遍完美匹配，然后药材选了，他的匹配点的药也要选。
证明：
1、可行解一定是这样的。
假设有一个可行解，左右大小都是i，因为左边选的，它的连边的右边一定选，所以i条匹配边一定在集合里面。所以药材的点的匹配边一定在集合里面。
2、这样做出来的答案一定左右大小相等
若左边大于右边，左边一定有一个点的匹配边在集合外，与左边的点的连边的点都选矛盾。
若左边小于右边，右边一定有一个点选了，但是没有选它的匹配点，与你的做法矛盾。
就是这样证明吧？
其实虽然我不会推出结论，但是这题的key的位置实在太明显了，脑洞再大一点就好了。毕竟这种题是证明还好，但是比较难以直接想到结论的。
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<iostream>
#include<algorithm>
#include<queue>
using namespace std;
#define Maxn 310
#define INF 0xfffffff
// #define LL long long int mymin(int x,int y) {return x<y?x:y;}
int n; struct node
{
int x,y,next,f,o;
}t[Maxn*Maxn*];
int first[Maxn],len; void ins(int x,int y,int f)
{
if(x==y) return;
t[++len].x=x;t[len].y=y;t[len].f=f;
t[len].next=first[x];first[x]=len;t[len].o=len+;
t[++len].x=y;t[len].y=x;t[len].f=;
t[len].next=first[y];first[y]=len;t[len].o=len-;
} queue<int > q;
int dis[Maxn],st,ed;
bool bfs()
{
while(!q.empty()) q.pop();
memset(dis,-,sizeof(dis));
q.push(st);dis[st]=;
while(!q.empty())
{
int x=q.front();
for(int i=first[x];i;i=t[i].next) if(t[i].f>)
{
int y=t[i].y;
if(dis[y]==-)
{
dis[y]=dis[x]+;
q.push(y);
}
}
q.pop();
}
return dis[ed]!=-;
} int ffind(int x,int flow)
{
if(x==ed) return flow;
int now=;
for(int i=first[x];i;i=t[i].next) if(t[i].f>)
{
int y=t[i].y;
if(dis[y]==dis[x]+)
{
int a=ffind(y,mymin(flow-now,t[i].f));
t[i].f-=a;
t[t[i].o].f+=a;
now+=a;
}
if(now==flow) break;
}
if(now==) dis[x]=-;
return now;
} int ans=;
void max_flow()
{
while(bfs())
{
ans-=ffind(st,INF);
}
} void output()
{
for(int i=;i<=len;i+=)
{
printf("%d -> %d %d\n",t[i].x,t[i].y,t[i].f);
}
} //-------------------------
int match[Maxn],chw[Maxn],g[Maxn][Maxn];
bool ffind2(int x,int nt)
{
for(int i=;i<=g[x][];i++)
{
int y=g[x][i];
if(chw[y]!=nt)
{
chw[y]=nt;
if(!match[y]||ffind2(match[y],nt))
{
match[y]=x;
return ;
}
}
}
return ;
} void get_match()
{
memset(chw,,sizeof(chw));
memset(match,,sizeof(match));
int nt=;
for(int i=;i<=n;i++)
{
ffind2(i,++nt);
}
} //------------------------- int main()
{
scanf("%d",&n);
st=n+;ed=st+;
bool ok=;int sm=;
for(int i=;i<=n;i++)
{
int x;
scanf("%d",&x);
g[i][]=x;
for(int j=;j<=x;j++)
{
int y;
scanf("%d",&y);
g[i][j]=y;
// ins(i,y,INF);
}
}
get_match();
// for(int i=1;i<=n;i++) printf("%d ",match[i]);printf("\n");
for(int i=;i<=n;i++)
for(int j=;j<=g[i][];j++)
{
ins(i,match[g[i][j]],INF);
}
for(int i=;i<=n;i++)
{
int w;
scanf("%d",&w);
w=-w;
if(w>) {ans+=w;ins(st,i,w);}
else ins(i,ed,-w);
}
// output();
max_flow();
printf("%d\n",-ans);
return ;
}
2017-04-09 21:36:14
