职务地址:http://acm.hdu.edu.cn/showproblem.php?pid=3081

有一段时间没写最大流的题了,这题建图竟然想了好长时间。。。刚開始是按着终于的最大流即是做多轮数去想建图,结果根本没思路。后来想了想,能够用二分答案的思想来找终于答案。然后非常明显的并查集,可是并查集学的略渣,竟然卡在并查集上了。。= =。 可是也不是并查集的事。。是我建图的思想太正了,略微用点逆向思维并查集就能够非常好利用了。

建图思路是:建立一个源点与汇点,将女孩与源点相连,男孩与汇点相连,权值均为二分得到的mid,然后将女孩男孩间能够建立关系的相连。权值均为1.最后推断是否满流。若满流,说明能够。就继续向上找。

代码例如以下:

#include

#include

#include

#include

#include

#include

#include

#include

#include

using namespace std;

const int INF=1e9;

int head[300], souce, sink, nv, cnt, n;

int cur[300], pre[300], d[300], q[300], bin[300], hash1[200][200], num[300];

struct no

{

int girl, boy;

}chao[20000];

int find1(int x)

{

return bin[x]==x?x:bin[x]=find1(bin[x]);

}

void merger(int x, int y)

{

int f1, f2;

f1=find1(x);

f2=find1(y);

if(f1!=f2)

{

bin[f2]=f1;

}

}

struct node

{

int u, v, cap, next;

}edge[1000000];

void add(int u, int v, int cap)

{

edge[cnt].v=v;

edge[cnt].cap=cap;

edge[cnt].next=head[u];

head[u]=cnt++;

edge[cnt].v=u;

edge[cnt].cap=0;

edge[cnt].next=head[v];

head[v]=cnt++;

}

void bfs()

{

memset(num,0,sizeof(num));

memset(d,-1,sizeof(d));

int f1=0, f2=0, i;

d[sink]=0;

num[0]=1;

q[f1++]=souce;

while(f1>=f2)

{

int u=q[f2++];

for(i=head[u];i!=-1;i=edge[i].next)

{

int v=edge[i].v;

if(d[v]==-1)

{

d[v]=d[u]+1;

num[d[v]]++;

q[f1++]=v;

}

}

}

}

int isap(int mid)

{

memcpy(cur,head,sizeof(cur));

bfs();

int i, u=pre[souce]=souce, flow=0;

while(d[souce]

{

//printf("%d\n",u);

if(u==sink)

{

int f=INF,pos;

for(i=souce;i!=sink;i=edge[cur[i]].v)

{

if(f>edge[cur[i]].cap)

{

f=edge[cur[i]].cap;

pos=i;

}

}

for(i=souce;i!=sink;i=edge[cur[i]].v)

{

edge[cur[i]].cap-=f;

edge[cur[i]^1].cap+=f;

}

flow+=f;

if(flow>=n*mid)

return flow;

u=pos;

}

for(i=cur[u];i!=-1;i=edge[i].next)

{

if(d[edge[i].v]+1==d[u]&&edge[i].cap)

break;

}

if(i!=-1)

{

cur[u]=i;

pre[edge[i].v]=u;

u=edge[i].v;

}

else

{

if(--num[d[u]]==0) break;

int mind=nv;

for(i=head[u];i!=-1;i=edge[i].next)

{

if(mind>d[edge[i].v]&&edge[i].cap)

{

mind=d[edge[i].v];

cur[u]=i;

}

}

d[u]=mind+1;

num[d[u]]++;

u=pre[u];

}

}

return flow;

}

int main()

{

int t, i, j, a, b, c, m, f;

scanf("%d",&t);

while(t--)

{

scanf("%d%d%d",&n,&m,&f);

for(i=1;i<=n;i++)

{

bin[i]=i;

}

for(i=1;i<=m;i++)

{

scanf("%d%d",&chao[i].girl,&chao[i].boy);

}

while(f--)

{

scanf("%d%d",&a,&b);

merger(a,b);

}

int low=0, high=n, mid, ans, x;

while(low<=high)

{

mid=(low+high)/2;

souce=0;

sink=2*n+1;

nv=sink+1;

memset(head,-1,sizeof(head));

memset(hash1,0,sizeof(hash1));

cnt=0;

for(i=1;i<=n;i++)

{

add(souce,i,mid);

add(i+n,sink,mid);

}

for(i=1;i<=m;i++)

{

int u=chao[i].girl;

int v=chao[i].boy;

for(j=1;j<=n;j++)

{

if(find1(u)==find1(j)&&!hash1[j][v])

{

hash1[j][v]=1;

add(j,v+n,1);

}

}

}

x=isap(mid);

//printf("%d\n",x);

if(x>=n*mid)

{

low=mid+1;

ans=mid;

}

else

{

high=mid-1;

}

}

printf("%d\n",ans);

}

return 0;

}

版权声明:本文博主原创文章,博客,未经同意不得转载。

好文阅读

评论可见,请评论后查看内容,谢谢!!!评论后请刷新页面。