首页 > 代码库 > 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 <iostream>  
#include <queue>  
using namespace std;  
const int maxN=2048;  
const int maxM=1000000;  
  
struct Edge  
{  
    int v,f,nxt;  
}e[maxM*2+10];  
queue<int> 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=http://www.mamicode.com/0,sink=n+m+1;>

poj 2289 Jamie's Contact Groups 二分+网络流