TOJ 3711 浪漫自习最大流

柔情只为你懂 2022-05-27 04:48 139阅读 0赞

如今的校园谈恋爱已是习以为常，这不，去上自习也要成双成对的。现在假设某班里有N对情侣从同一寝室楼出发，到达同一个教室上自习。途中，她们可能会经过长廊、静溪等一系列的景点观光游览。但情侣们不希望在途中碰到班里的其他情侣而扫了雅兴。现在给定包括寝室、教室、以及各个景点在内共有M个场景，以及这些场景之间的路径分布情况，请您帮忙为情侣们设计各自单独的散步路线。

![3711.jpg][]

输入

输入数据有多组，每组数据的第一行为2个正整数N（1<=N<=50）和M（2<=M<=50），分别表示共有N对情侣，M个场景，我们对场景从1~M进行编号。接下来的M行中，其中第i行的第一个数为正整数K，后面有K个正整数，表示与第i个场景之间有路径相连的场景编号。场景之间的路径是双向的，因此如果a与b之间有路径，那么b与a之间也必然有路径。我们始终假设：编号为1的场景是出发地——寝室楼，编号为2的场景是情侣们的目的地——自习教室。

当N和M均为0时输入结束。

输出

如果能够为情侣们设计出各自单独的散步路线（即除了出发地和目的地外，之间永远不会碰面），那么请输出YES，否则输出NO。

![20180411205851597][]

提示

样例的第一个实例对应的解决方案是：

1->3->2

1->4->2

1->5->2

![3711-2.jpg][]

把联通的路径设为1，直接求最大流就可以了。

#include<stdio.h>
    #include<string.h>
    #include<math.h>
    #include<iostream>
    #include<string>
    #include<algorithm>
    #include<map>
    #include<queue>
    #include<vector>
    using namespace std;
    const int inf=0x7f7f7f7f;
    int n,m,G[55][55],flow[55],pre[55];
    queue<int> q;
    int bfs(int s,int t)
    {
    	while(!q.empty())
    	q.pop();
    	memset(pre,-1,sizeof pre);
    	pre[s]=0,flow[s]=inf;
    	q.push(s);
    	while(!q.empty())
    	{
    		int p=q.front();
    		q.pop();
    		if(p==t)break;
    		for(int u=1;u<=n;u++)
    		{
    			if(u!=s&&G[p][u]>0&&pre[u]==-1)
    			{
    				pre[u]=p;
    				flow[u]=min(flow[p],G[p][u]);
    				q.push(u);
    			}
    		}
    	}
    	if(pre[t]==-1)return -1;
    	return flow[t];
    }
    int EK(int s,int t)
    {
    	int delta=0,tot=0;
    	while(1)
    	{
    		delta=bfs(s,t); 
    		if(delta==-1)break;
    		int p=t;
    		while(p!=s)
    		{
    			G[pre[p]][p]-=delta;
    			G[p][pre[p]]+=delta;
    			p=pre[p];
    		}
    		tot+=delta;
    	}
    	return tot;
    }
    int main()
    {
    	int i,j,t,tl;
    	while(scanf("%d%d",&m,&n))
    	{
    		if(n==0&&m==0)break;
    		memset(G,0,sizeof G);		
    		memset(flow,0,sizeof flow);		
    		for(i=1;i<=n;i++)
    		{
    			scanf("%d",&t);
    			for(j=0;j<t;j++)
    			{
    				scanf("%d",&tl);
    				G[i][tl]=G[tl][i]=1;
    			}
    		}
    		//printf("%d\n",EK(1,2));
    		int sum=EK(1,2);
    		if(sum>=m)
    		printf("YES\n");
    		else
    		printf("NO\n");
    	}
    }

[3711.jpg]: http://acm.tzc.edu.cn/acmhome/judge/images/3711.jpg
[20180411205851597]: /images/20220527/6aa1677978f9415b8e4725e8617984b9.png
[3711-2.jpg]: http://acm.tzc.edu.cn/acmhome/judge/images/3711-2.jpg