首页 > 代码库 > POJ 3281 网络流（dinic邻接矩阵、单路增广、多路增广）
POJ 3281 网络流（dinic邻接矩阵、单路增广、多路增广）
思路：刚开始看题就想到怎么建图了，源点连向所有的食物，食物连牛，牛连饮料，饮料连汇点，所有的流量都是1.不过这样建图好后，WA了。原来是一头牛只能单一匹配一组食物和饮料，所以牛得拆点，牛之间得相连，流量为1，以保证单一匹配食物和饮料。
邻接矩阵dinic单路的代码：
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<map>
#include<queue>
#include<set>
#include<cmath>
#include<bitset>
#define mem(a,b) memset(a,b,sizeof(a))
#define lson i<<1,l,mid
#define rson i<<1|1,mid+1,r
#define llson j<<1,l,mid
#define rrson j<<1|1,mid+1,r
#define INF 0x7fffffff
#define maxn 20005
typedef long long ll;
typedef unsigned long long ull;
using namespace std;
int n,m,d[maxn],Map[501][501];
int bfs()
{
mem(d,-1);
queue<int>q; q.push(0); d[0]=0;
while(!q.empty()) //找增广路
{
int u=q.front(); q.pop();
for(int v=0;v<=n;v++)
{
if(d[v]==-1&&Map[u][v])
{
d[v]=d[u]+1; //分层，越往后，层数越大
q.push(v);
}
}
}
return d[n]!=-1;
}
int dfs(int u,int Min)
{
int sum;
if(u==n) return Min;
for(int v=0;v<=n;v++)
if(Map[u][v]&&d[v]==d[u]+1&&(sum=dfs(v,min(Min,Map[u][v]))))
{
Map[u][v]-=sum;
Map[v][u]+=sum;
return sum;
}
return 0;
}
int Dinic()
{
int tmp,ans=0;
while(bfs())
{
while(tmp=dfs(0,INF))
ans+=tmp;
}
return ans;
}
int main()
{
//freopen("1.txt","r",stdin);
int N,F,D,ff,dd,i,j,mm;
scanf("%d%d%d",&N,&F,&D);
for(i=1;i<=N;i++)
{
scanf("%d%d",&ff,&dd);
for(j=0;j<ff;j++)
{
scanf("%d",&mm);
Map[mm+N*2][i]=1;
}
for(j=0;j<dd;j++)
{
scanf("%d",&mm);
Map[i+N][mm+N*2+F]=1;
}
Map[i][i+N]=1;//牛之间自连，保存每头牛只匹配一组食物和饮料
}
for(i=N*2+1;i<=N*2+F;i++)
Map[0][i]=1;//连源点
n=N*2+F+D+1;
for(i=N*2+F+1;i<=N*2+F+D;i++)
Map[i][n]=1;//连汇点
printf("%d\n",Dinic());
return 0;
}
dinic单路增广代码：#pragma comment(linker, "/STACK:1024000000,1024000000")
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<map>
#include<queue>
#include<set>
#include<cmath>
#include<bitset>
#define mem(a,b) memset(a,b,sizeof(a))
#define lson i<<1,l,mid
#define rson i<<1|1,mid+1,r
#define llson j<<1,l,mid
#define rrson j<<1|1,mid+1,r
#define INF 0x7fffffff
typedef long long ll;
typedef unsigned long long ull;
using namespace std;
#define maxn 2000005
int n,cnt,d[maxn],head[maxn],go[maxn],q[maxn];
struct node
{
int v,w,next;
}e[maxn];
void add(int u,int v,int w)
{
e[cnt].v=v; e[cnt].w=w; go[cnt]=cnt+1;
e[cnt].next=head[u]; head[u]=cnt++;
e[cnt].v=u; e[cnt].w=0; go[cnt]=cnt-1;//刚开始反向边权值写成w了一直wa
e[cnt].next=head[v]; head[v]=cnt++;
}
int bfs()
{
mem(d,-1);
int l=0,r=0;
q[r++]=0; d[0]=0;
while(l<r) //找增广路
{
int u=q[l++];
for(int v=head[u];v!=-1;v=e[v].next)
{
if(d[e[v].v]==-1&&e[v].w)
{
d[e[v].v]=d[u]+1; //分层，越往后，层数越大
if(e[v].v!=n+1) q[r++]=e[v].v;
}
}
}
return d[n]!=-1;
}
int dfs(int u,int Min)
{
int sum;
if(u==n) return Min;
for(int v=head[u];v!=-1;v=e[v].next) //Min-duolu这个多路增广的做法真神！
if(e[v].w&&d[e[v].v]==d[u]+1&&(sum=dfs(e[v].v,min(Min,e[v].w))))
{
e[v].w-=sum;
e[go[v]].w+=sum;
return sum;
}
return 0;
}
void init()
{
mem(head,-1),mem(go,0),cnt=0;
}
int Dinic()
{
int tmp,ans=0;
while(bfs())
{
while(tmp=dfs(0,INF)) ans+=tmp;
}
return ans;
}
int main()
{
//freopen("1.txt","r",stdin);
int N,F,D,ff,dd,i,j,mm;
scanf("%d%d%d",&N,&F,&D);
init();
for(i=1;i<=N;i++)
{
scanf("%d%d",&ff,&dd);
for(j=0;j<ff;j++)
{
scanf("%d",&mm);
add(mm+N*2,i,1);
}
for(j=0;j<dd;j++)
{
scanf("%d",&mm);
add(i+N,mm+N*2+F,1);
}
add(i,i+N,1);//牛之间自连，保存每头牛只匹配一组食物和饮料
}
for(i=N*2+1;i<=N*2+F;i++)
add(0,i,1);//连源点
n=N*2+F+D+1;
for(i=N*2+F+1;i<=N*2+F+D;i++)
add(i,n,1);//连汇点
printf("%d\n",Dinic());
return 0;
}
Dinic多路增广代码：#pragma comment(linker, "/STACK:1024000000,1024000000")
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<map>
#include<queue>
#include<set>
#include<cmath>
#include<bitset>
#define mem(a,b) memset(a,b,sizeof(a))
#define lson i<<1,l,mid
#define rson i<<1|1,mid+1,r
#define llson j<<1,l,mid
#define rrson j<<1|1,mid+1,r
#define INF 0x7fffffff
typedef long long ll;
typedef unsigned long long ull;
using namespace std;
#define maxn 2000005
int n,cnt,d[maxn],head[maxn],go[maxn],q[maxn];
struct node
{
int v,w,next;
}e[maxn];
void add(int u,int v,int w)
{
e[cnt].v=v; e[cnt].w=w; go[cnt]=cnt+1;
e[cnt].next=head[u]; head[u]=cnt++;
e[cnt].v=u; e[cnt].w=0; go[cnt]=cnt-1;//刚开始反向边权值写成w了一直wa
e[cnt].next=head[v]; head[v]=cnt++;
}
int bfs()
{
mem(d,-1);
int l=0,r=0;
q[r++]=0; d[0]=0;
while(l<r) //找增广路
{
int u=q[l++];
for(int v=head[u];v!=-1;v=e[v].next)
{
if(d[e[v].v]==-1&&e[v].w)
{
d[e[v].v]=d[u]+1; //分层，越往后，层数越大
if(e[v].v!=n+1) q[r++]=e[v].v;
}
}
}
return d[n]!=-1;
}
int dfs(int u,int Min)
{
int sum,duolu=0;
if(u==n) return Min;
for(int v=head[u];v!=-1&&Min-duolu>0;v=e[v].next) //Min-duolu这个多路增广的做法真神！
if(e[v].w&&d[e[v].v]==d[u]+1&&(sum=dfs(e[v].v,min(Min-duolu,e[v].w))))
{
e[v].w-=sum;
e[go[v]].w+=sum;
duolu+=sum;
}
return duolu;
}
void init()
{
mem(head,-1),mem(go,0),cnt=0;
}
int Dinic()
{
int tmp,ans=0;
while(bfs())
{
while(tmp=dfs(0,INF)) ans+=tmp;
}
return ans;
}
int main()
{
//freopen("1.txt","r",stdin);
int N,F,D,ff,dd,i,j,mm;
scanf("%d%d%d",&N,&F,&D);
init();
for(i=1;i<=N;i++)
{
scanf("%d%d",&ff,&dd);
for(j=0;j<ff;j++)
{
scanf("%d",&mm);
add(mm+N*2,i,1);
}
for(j=0;j<dd;j++)
{
scanf("%d",&mm);
add(i+N,mm+N*2+F,1);
}
add(i,i+N,1);//牛之间自连，保存每头牛只匹配一组食物和饮料
}
for(i=N*2+1;i<=N*2+F;i++)
add(0,i,1);//连源点
n=N*2+F+D+1;
for(i=N*2+F+1;i<=N*2+F+D;i++)
add(i,n,1);//连汇点
printf("%d\n",Dinic());
return 0;
}
POJ 3281 网络流（dinic邻接矩阵、单路增广、多路增广）
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。