本文主要是介绍最大流-Dinic，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
pos 1274
Dinic写的二分图
#include <iostream>
#include <vector>
#include <cstdio>
#include <cstring>
#include <queue>
using namespace std;
const int maxn = 500;
const int INF = 1 << 20;
struct edge{
int u,v,cap,flow;
edge(int u,int v,int c,int f) :u(u),v(v),cap(c),flow(f) {}
};
struct dinic{
int n,m,s,t;
vector<edge> es;
vector<int> mp[maxn];
int d[maxn];
int cur[maxn];
bool vis[maxn];
void init(){
for(int i = 1;i <= n;i ++)
{
mp[i].clear();
}
es.clear();
}
void addedge(int u,int v,int c){
es.push_back(edge(u,v,c,0));
es.push_back(edge(v,u,0,0));
m = es.size();
mp[u].push_back(m - 2);
mp[v].push_back(m - 1);
}
bool bfs()//对残量网络中的点bfs
{
memset(vis, 0, sizeof(vis));
queue<int> q;
q.push(s);
vis[s] = 1;
d[s] = 0;
while(!q.empty())
{
int x = q.front();
q.pop();
for(int i = 0;i < mp[x].size();i ++)
{
edge &e = es[mp[x][i]];
if(!vis[e.v] && e.cap > e.flow)
{
vis[e.v] = 1;
d[e.v] = d[x] + 1;
q.push(e.v);
}
}
}
return vis[t];
}
int dfs(int x,int a)//当前节点x 路径上最小增量a
{
if(x == t || a == 0) return a;
int flow = 0,f;
for(int &i = cur[x];i < mp[x].size();i ++)
{
edge &e = es[mp[x][i]];
if(d[x] + 1 == d[e.v] && (f = dfs(e.v,min((e.cap - e.flow),a))) > 0)//
{
e.flow += f;
es[mp[x][i] ^ 1].flow -= f;
flow += f;
a -= f;
if(a == 0) break;
}
}
return flow;
}
int maxflow(){
int flow = 0;
while(bfs())
{
memset(cur, 0, sizeof(cur));
flow += dfs(s,INF);
}
return flow;
}
};
int main()
{
int n,m;
while( cin >> n >> m){
dinic di;
di.n = n + m + 2;
int s = n + m + 1,t = s + 1;
di.s = s;di.t = t;
for(int i = 1;i <= n;i ++)
{
int sz,tmp;
scanf("%d",&sz);
for (int j = 0; j < sz; j ++) {
scanf("%d",&tmp);
di.addedge(i, tmp + n, 1);
}
di.addedge(s, i, 1);
}
for (int i = 1; i <= m; i ++) {
di.addedge(n + i, t, 1);
}
cout << di.maxflow() << endl;
}
return 0;
}
这篇关于最大流-Dinic的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
