poj 2289 Jamie's Contact Groups 二分+網絡流

poj 2289 Jamie's Contact Groups 二分+網絡流

題意：

讓n個點和m個點對應，一個n只能對應一個m,一個m可以對應多個n,對每個n給出他能對應的m點集合，求m對應n多數的最小值。

分析：

網絡流+二分。

代碼：

//poj 2289
//sep9
#include   
#include   
using namespace std;  
const int maxN=2048;  
const int maxM=1000000;  
  
struct Edge  
{  
    int v,f,nxt;  
}e[maxM*2+10];  
queue que;  
int src,sink;  
int g[maxN+10];  
int nume;  
bool vis[maxN+10];  
int dist[maxN+10];  
int map[2048][2048]; 
int n,m;
char tmp[4000];
void addedge(int u,int v,int c)  
{  
    e[++nume].v=v;e[nume].f=c;e[nume].nxt=g[u];g[u]=nume;  
    e[++nume].v=u;e[nume].f=0;e[nume].nxt=g[v];g[v]=nume;  
}  
  
void init()  
{  
    memset(g,0,sizeof(g));    
    nume=1;  
}  
  
void bfs()  
{  
    while(!que.empty()) que.pop();  
    vis[src]=true;  
    que.push(src);    
    while(!que.empty()){  
        int u=que.front();que.pop();  
        for(int i=g[u];i;i=e[i].nxt)  
            if(e[i].f&&!vis[e[i].v]){  
                que.push(e[i].v);  
                dist[e[i].v]=dist[u]+1;  
                vis[e[i].v]=true;   
            }  
    }  
}  
  
int dfs(int u,int delta)  
{  
    if(u==sink)  
        return delta;  
    int ret=0;  
    for(int i=g[u];delta&&i;i=e[i].nxt)  
        if(e[i].f&&dist[e[i].v]==dist[u]+1){  
            int dd=dfs(e[i].v,min(e[i].f,delta));  
            e[i].f-=dd;  
            e[i^1].f+=dd;  
            delta-=dd;  
            ret+=dd;  
        }     
    return ret;  
}  
  
int dinic(int maxx)  
{  
	init();    
    src=0,sink=n+m+1;
	int i,j;
	for(i=1;i<=n;++i)
		addedge(src,i,1);
	for(i=1;i<=n;++i)
		for(j=1;j<=m;++j)
			if(map[i][j]==1)
				addedge(i,n+j,1);
	for(i=1;i<=m;++i)
		addedge(n+i,sink,maxx);
	int ret=0;  
    while(1){  
        memset(vis,0,sizeof(vis));  
        memset(dist,0,sizeof(dist));  
        bfs();  
        if(!vis[sink]) break;  
        ret+=dfs(src,INT_MAX);  
    } 
	if(ret==n) 
    	return 1;   
	return 0;
}  
  
int main()  
{  
	while(scanf("%d%d",&n,&m)==2){
		if(n==0&&m==0)
			break;
		int i,j;
		getchar();
		memset(map,0,sizeof(map));
      	for(int i=1;i<=n;i++)
      	{
       		gets(tmp);
         	int len=strlen(tmp);
          	for(int j=0;j='0'&&tmp[j]<='9')
             	{
              		int  v=0;
                	while(tmp[j]>='0'&&tmp[j]<='9')
                 	{
                         v=v*10+tmp[j++]-'0';
                  	}
                    map[i][v+1]=1;
                }
            }
        }
		int ans,l,r;
		l=0,r=n+1;
		while(l