首页 > 代码库 > 一些网络流。
一些网络流。
POJ 3281
题意：每一头牛都有它喜欢吃的食物和饮料，问最多能满足多少头牛 让它吃到它喜欢吃的食物和饮料。
思路：从源点S对每一个食物连一条边，容量为1， 然后食物对喜欢吃这种食物的牛连边，容量也为1，然后每头牛连一条边到喜欢吃的饮料 容量也为1。
每个饮料连边到汇点，容量为1。 这样图构好了，但是每头牛可能会产生吃多个食物或者多个饮料的情况，所以对牛这个点也要进行限制。每头牛限制通过的流量为1
把牛拆成两个点 中间连一条容量为1的边，每个点分别连着食物和饮料，这样求一个最大流就行了。
#include<stdio.h>
#include<string.h>
#include<algorithm>
#include<vector>
#include<queue>
#include<iostream>
#define INF 100000000
using namespace std;
struct edge{
int to;
int cap;
int rav;
};
vector<edge> G[808];
int level[808];
int iter[808];
int n,f,d;
void add_edge(int from,int to,int cap)
{
G[from].push_back((edge){to,cap,G[to].size()});
G[to].push_back((edge){from,0,G[from].size()-1});
}
void bfs(int s)
{
queue<int> q;
memset(level,-1,sizeof(level));
level[s]=0;
q.push(s);
while(!q.empty())
{
int u=q.front();
q.pop();
for(int i=0;i<G[u].size();i++)
{
edge &e=G[u][i];
if(e.cap>0&&level[e.to]<0)
{
level[e.to]=level[u]+1;
q.push(e.to);
}
}
}
}
int dfs(int v,int t,int f)
{
if(v==t) return f;
for(int &i=iter[v];i<G[v].size();i++)
{
edge &e=G[v][i];
if(e.cap>0&&level[v]<level[e.to])
{
int d=dfs(e.to,t,min(f,e.cap));
if(d>0)
{
e.cap-=d;
G[e.to][e.rav].cap+=d;
return d;
}
}
}
return 0;
}
int max_flow(int s,int t)
{
int flow=0;
while(1)
{
bfs(s);
if(level[t]<0) return flow;
memset(iter,0,sizeof(iter));
int f;
while((f=dfs(s,t,INF))>0)
flow+=f;
}
}
int main()
{
while(scanf("%d%d%d",&n,&f,&d)!=EOF)
{
for(int i=0;i<=(n+n+f+d);i++)
G[i].clear();
for(int i=1;i<=f;i++)
add_edge(0,i,1);
for(int i=1;i<=n;i++)
{
int f1,d1;
scanf("%d%d",&f1,&d1);
for(int j=0;j<f1;j++)
{
int p;
scanf("%d",&p);
add_edge(p,i+f,1);
}
add_edge(i+f,i+n+f,1);
for(int j=0;j<d1;j++)
{
int p;
scanf("%d",&p);
add_edge(i+n+f,p+n+n+f,1);
}
}
for(int i=1;i<=d;i++)
add_edge(i+n+n+f,n+n+f+d+1,1);
int ans;
int k=2*n+f+d+1;
ans=max_flow(0,k);
printf("%d\n",ans);
}
}POJ 2135
题意：一个农夫从1号农田到N号农田 走一个来回 要求不走相同的路且最短。
思路：建立最小费用流模型，距离为消费，容量为1，然后求1-N流量为2的最小费用就行了。
#include<stdio.h>
#include<string.h>
#include<algorithm>
#include<vector>
#include<queue>
#include<stack>
#include<iostream>
#define INF 1000000000
using namespace std;
struct edge
{
int to;
int cap;
int cost;
int rav;
};
vector<edge> G[1005];
int dist[1005];
int n;
int prevv[1005];
int preve[1005];
bool inque[1005];
void add_edge(int from,int to,int cap,int cost)
{
G[from].push_back((edge){to,cap,cost,G[to].size()});
G[to].push_back((edge){from,0,-cost,G[from].size()-1});
}
int min_liu(int s,int t,int f)
{
int res=0;
while(f>0)
{
fill(dist,dist+n,INF);
memset(inque,0,sizeof(inque));
dist[s]=0;
queue<int> q;
inque[s]=1;
q.push(s);
while(!q.empty())
{
int u=q.front();
q.pop();
inque[u]=0;
for(int i=0;i<G[u].size();i++)
{
edge &e=G[u][i];
//cout<<u<<" "<<e.to<<" "<<e.cap<<" "<<e.cost<<" "<<dist[e.to]<<" "<<dist[u]+e.cost<<endl;
if(e.cap>0&&dist[e.to]>dist[u]+e.cost)
{
dist[e.to]=dist[u]+e.cost;
prevv[e.to]=u;
preve[e.to]=i;
if(!inque[e.to])
{
inque[e.to]=1;
q.push(e.to);
}
}
}
}
//cout<<endl;
if(dist[t]==INF) return -1;
res+=dist[t];
for(int v=t;v!=s;v=prevv[v])
{
edge &e=G[prevv[v]][preve[v]];
//cout<<prevv[v]<<endl;
e.cap--;
G[v][e.rav].cap++;
//cout<<v<<" "<<G[v][e.rav].to<<endl;
}
f--;
}
return res;
}
int main()
{
int m;
while(scanf("%d%d",&n,&m)!=EOF)
{
for(int i=0;i<n;i++)
G[i].clear();
while(m--)
{
int a,b,c;
scanf("%d%d%d",&a,&b,&c);
add_edge(a-1,b-1,1,c);
add_edge(b-1,a-1,1,c);
}
printf("%d\n",min_liu(0,n-1,2));
}POJ 3686
题意：有一些玩具和一些工厂 每个玩具在不同的工厂加工的时间不同，问平均时间最短多少。
思路：对于一个工厂 如果有k个玩具加工 总时间为T=k*a1+(k-1)*a2+......1*ak;
我们可以把每个工厂的点拆成N个，每个玩具对第i个工厂的第j个点连边 费用为 j*Zx.表示这个玩具在这个工厂第j个加工。
然后求一个最小费用就行了。
#include<stdio.h>
#include<string.h>
#include<algorithm>
#include<iostream>
#include<queue>
#include<stack>
#include<math.h>
#include<vector>
#define INF 1000000000
using namespace std;
struct edge{
int to;
int cap;
int cost;
int rav;
};
vector<edge> G[3005];
void add_edge(int from,int to,int cap,int cost)
{
G[from].push_back((edge){to,cap,cost,G[to].size()});
G[to].push_back((edge){from,0,-cost,G[from].size()-1});
}
int dist[3005];
bool inque[3005];
int prevv[3005];
int preve[3005];
int min_liu(int s,int t,int f)
{
int res=0;
while(f>0)
{
queue<int> q;
fill(dist,dist+t+1,INF);
dist[s]=0;
q.push(s);
inque[s]=1;
while(!q.empty())
{
int u=q.front();
q.pop();
inque[u]=0;
for(int i=0;i<G[u].size();i++)
{
edge &e=G[u][i];
if(e.cap>0&&dist[e.to]>dist[u]+e.cost)
{
dist[e.to]=dist[u]+e.cost;
prevv[e.to]=u;
preve[e.to]=i;
if(!inque[e.to])
{
inque[e.to]=1;
q.push(e.to);
}
}
}
}
if(dist[t]==INF) return -1;
int d=INF;
for(int v=t;v!=s;v=prevv[v])
d=min(d,G[prevv[v]][preve[v]].cap);
f-=d;
res+=d*dist[t];
for(int v=t;v!=s;v=prevv[v])
{
edge &e=G[prevv[v]][preve[v]];
e.cap-=d;
G[v][e.rav].cap+=d;
}
}
return res;
}
int k[105][105];
int main()
{
int t;
scanf("%d",&t);
while(t--)
{
//printf("\n");
int n,m;
scanf("%d%d",&n,&m);
for(int i=0;i<n*m+n+2;i++)
G[i].clear();
for(int i=1;i<=n;i++)
add_edge(0,i,1,0);
for(int i=0;i<n;i++)
for(int j=0;j<m;j++)
scanf("%d",&k[i][j]);
for(int i=0;i<n;i++)
{
for(int j=0;j<m;j++)
{
for(int k1=1;k1<=n;k1++)
{
add_edge(i+1,n+k1+j*n,1,k1*k[i][j]);
}
}
}
for(int i=n+1;i<=(m+1)*n;i++)
add_edge(i,(m+1)*n+1,1,0);
double k=min_liu(0,(m+1)*n+1,n);
printf("%.6f\n",k/(double)n);
}
}POJ 1698
题意： 有一些电影要拍，每个电影只能在特定的星期开拍，并且需要在多少个星期内拍完，问能否拍完。
思路： 每个电影对 他能拍的那一天连边 容量为1。 源点对电影连边 容量为电影需要拍的次数。然后每一天对汇点连边，容量为1，判断最大流是否为电影拍的总和即可。
#include<stdio.h>
#include<string.h>
#include<algorithm>
#include<iostream>
#include<vector>
#include<queue>
#include<stack>
#include<math.h>
#include<deque>
#define INF 1000000000
using namespace std;
struct edge{
int to;
int cap;
int rav;
};
vector<edge> G[505];
int level[505];
int iter[505];
void add_edge(int from,int to,int cap)
{
G[from].push_back((edge){to,cap,G[to].size()});
G[to].push_back((edge){from,0,G[from].size()-1});
}
void bfs(int s)
{
queue<int> q;
q.push(s);
memset(level,-1,sizeof(level));
level[s]=0;
while(!q.empty())
{
int u=q.front();
q.pop();
for(int i=0;i<G[u].size();i++)
{
edge &e=G[u][i];
if(e.cap>0&&level[e.to]<0)
{
level[e.to]=level[u]+1;
q.push(e.to);
}
}
}
}
int dfs(int v,int t,int f)
{
if(v==t) return f;
for(int &i=iter[v];i<G[v].size();i++)
{
edge &e=G[v][i];
if(e.cap>0&&level[v]<level[e.to])
{
int d=dfs(e.to,t,min(f,e.cap));
if(d>0)
{
e.cap-=d;
G[e.to][e.rav].cap+=d;
return d;
}
}
}
return 0;
}
int max_flow(int s,int t)
{
int res=0;
while(1)
{
bfs(s);
if(level[t]==-1) return res;
memset(iter,0,sizeof(iter));
int f;
while((f=dfs(s,t,INF))>0)
res+=f;
}
return res;
}
bool vis[25][10];
int main()
{
int t;
scanf("%d",&t);
while(t--)
{
memset(vis,0,sizeof(vis));
int n;
scanf("%d",&n);
for(int i=0;i<500;i++)
G[i].clear();
int l=n+1;
int ma=0;
int sum=0;
for(int i=0;i<n;i++)
{
for(int j=0;j<7;j++)
scanf("%d",&vis[i][j]);
int f;
scanf("%d",&f);
add_edge(0,i+1,f);
sum+=f;
int w;
scanf("%d",&w);
for(int j=0;j<w;j++)
{
for(int k=0;k<7;k++)
{
int s=j*7+k;
ma=max(ma,s);
if(vis[i][k])
add_edge(i+1,l+s,1);
}
}
}
for(int i=l;i<=ma+l;i++)
add_edge(i,500,1);
if(max_flow(0,500)==sum)
printf("Yes\n");
else printf("No\n");
}
}POJ 2112
题意： 有K个挤奶机和C头牛，每头挤奶机最多只能支持M头牛挤奶，求使得所走路程最远的奶牛路程最短的方案。
思路：先用floyd求点与点之间最短路，源点对每台挤奶机连一条容量为M的边，然后二分路程长度，每次把长度小于等于该长度的边连起来，然后用最大流判断是否可行。
#include<stdio.h>
#include<string.h>
#include<algorithm>
#include<vector>
#include<queue>
#include<iostream>
#include<math.h>
#define INF 100000000
using namespace std;
struct edge{
int to;
int cap;
int rav;
};
vector<edge> G[305];
int level[305];
int iter[305];
void add_edge(int from,int to,int cap)
{
G[from].push_back((edge){to,cap,G[to].size()});
G[to].push_back((edge){from,0,G[from].size()-1});
}
void bfs(int s)
{
memset(level,-1,sizeof(level));
queue<int> q;
q.push(s);
level[s]=0;
while(!q.empty())
{
int u=q.front();
q.pop();
for(int i=0;i<G[u].size();i++)
{
edge &e=G[u][i];
if(e.cap>0&&level[e.to]<0)
{
level[e.to]=level[u]+1;
q.push(e.to);
}
}
}
}
int dfs(int u,int t,int f)
{
if(u==t) return f;
for(int &i=iter[u];i<G[u].size();i++)
{
edge &e=G[u][i];
if(e.cap>0&&level[e.to]>level[u])
{
int d=dfs(e.to,t,min(f,e.cap));
if(d>0)
{
e.cap-=d;
G[e.to][e.rav].cap+=d;
return d;
}
}
}
return 0;
}
int max_flow(int s,int t)
{
int res=0;
while(1)
{
bfs(s);
if(level[t]<0) return res;
int f;
memset(iter,0,sizeof(iter));
while((f=dfs(s,t,INF))>0)
res+=f;
}
}
int k[305][305];
void floyd(int n)
{
for(int k1=0;k1<n;k1++)
for(int i=0;i<n;i++)
for(int j=0;j<n;j++)
{
k[i][j]=min(k[i][j],k[i][k1]+k[k1][j]);
}
}
void CLEAR(int l,int r)
{
for(int i=l;i<=r;i++)
G[i].clear();
}
int main()
{
int K,N,M;
while(scanf("%d%d%d",&K,&N,&M)!=EOF)
{
CLEAR(0,K+N+1);
int n=K+N;
for(int i=0;i<n;i++)
for(int j=0;j<n;j++)
{
scanf("%d",&k[i][j]);
if(i!=j&&!k[i][j])
k[i][j]=INF;
}
floyd(n);
int l=0,r=20000;
int now;
while(1)
{
CLEAR(0,K+N+1);
for(int i=1;i<=K;i++)
add_edge(0,i,M);
for(int i=K+1;i<=n;i++)
add_edge(i,K+N+1,1);
now=(l+r)>>1;
for(int i=0;i<K;i++)
for(int j=K;j<n;j++)
{
if(k[i][j]<=now)
add_edge(i+1,j+1,1);
}
int f=max_flow(0,n+1);
//cout<<f<<" "<<now<<endl;
if(f==N)
{
r=now;
}
else l=now+1;
if(l>=r) break;
}
printf("%d\n",r);
}
}
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。