首页 > 代码库 > 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 二分+网络流
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。