P3376 【模板】网络最大流(70)
2018-06-17 22:14:33来源:未知 阅读 ()
题目描述
如题,给出一个网络图,以及其源点和汇点,求出其网络最大流。
输入输出格式
输入格式:
第一行包含四个正整数N、M、S、T,分别表示点的个数、有向边的个数、源点序号、汇点序号。
接下来M行每行包含三个正整数ui、vi、wi,表示第i条有向边从ui出发,到达vi,边权为wi(即该边最大流量为wi)
输出格式:
一行,包含一个正整数,即为该网络的最大流。
输入输出样例
4 5 4 3 4 2 30 4 3 20 2 3 20 2 1 30 1 3 40
50
说明
时空限制:1000ms,128M
数据规模:
对于30%的数据:N<=10,M<=25
对于70%的数据:N<=200,M<=1000
对于100%的数据:N<=10000,M<=100000
样例说明:
题目中存在3条路径:
4-->2-->3,该路线可通过20的流量
4-->3,可通过20的流量
4-->2-->1-->3,可通过10的流量(边4-->2之前已经耗费了20的流量)
故流量总计20+20+10=50。输出50。
莫名其妙WA三个点,
改天再调
1 #include<iostream> 2 #include<cstdio> 3 #include<cstring> 4 #include<cmath> 5 #include<queue> 6 #include<algorithm> 7 #define lli long long int 8 using namespace std; 9 const int MAXN=300001; 10 const int maxn=0x7ffffff; 11 void read(int &n) 12 { 13 char c='+';int x=0;bool flag=0; 14 while(c<'0'||c>'9') 15 {c=getchar();if(c=='-')flag=1;} 16 while(c>='0'&&c<='9') 17 {x=x*10+c-48;c=getchar();} 18 flag==1?n=-x:n=x; 19 } 20 struct node 21 { 22 int u,v,flow,cap,nxt; 23 }edge[MAXN]; 24 int head[MAXN]; 25 int num=1; 26 int n,m,S,T; 27 int dis[MAXN]; 28 int vis[MAXN]; 29 int cur[MAXN]; 30 void add_edge(int x,int y,int z) 31 { 32 edge[num].u=x; 33 edge[num].v=y; 34 edge[num].cap=z; 35 edge[num].flow=0; 36 edge[num].nxt=head[x]; 37 head[x]=num++; 38 } 39 bool bfs(int bg,int ed) 40 { 41 memset(vis,0,sizeof(vis)); 42 memset(dis,0,sizeof(dis)); 43 queue<int>q; 44 q.push(bg); 45 dis[bg]=1; 46 vis[bg]=1; 47 while(!q.empty()) 48 { 49 int p=q.front(); 50 q.pop(); 51 for(int i=head[p];i!=-1;i=edge[i].nxt) 52 { 53 if(!vis[edge[i].v]&&edge[i].cap-edge[i].flow>0) 54 { 55 vis[edge[i].v]=1; 56 dis[edge[i].v]=dis[edge[i].u]+1; 57 q.push(edge[i].v); 58 } 59 } 60 } 61 return vis[ed]; 62 } 63 int dfs(int now,int a)// a:所有弧的最小残量 64 { 65 if(now==T||a<=0) 66 return a; 67 int flow=0,f; 68 for(int i=head[now];i!=-1;i=edge[i].nxt) 69 { 70 if(dis[now]+1==dis[edge[i].v]&&edge[i].cap-edge[i].flow>0) 71 { 72 f=dfs(edge[i].v,min(a,edge[i].cap-edge[i].flow)); 73 edge[i].flow+=f; 74 edge[i^1].flow-=f; 75 flow+=f; 76 a-=f; 77 if(a<=0)break; 78 } 79 } 80 return flow; 81 } 82 void Dinic(int S,int T) 83 { 84 int ansflow=0; 85 //for(int i=1;i<=n;i++) 86 // cur[i]=head[i]; 87 while(bfs(S,T)) 88 { 89 ansflow+=dfs(S,maxn); 90 }// 求出层级 91 printf("%d",ansflow); 92 93 } 94 int main() 95 { 96 read(n);read(m); 97 // swap(n,m); 98 // S=1;T=m; 99 read(S);read(T); 100 for(int i=1;i<=n;i++) 101 head[i]=-1; 102 for(int i=1;i<=m;i++) 103 { 104 int x,y,z; 105 read(x);read(y);read(z); 106 add_edge(x,y,z); 107 add_edge(y,x,0); 108 } 109 Dinic(S,T); 110 return 0; 111 }
标签:
版权申明:本站文章部分自网络,如有侵权,请联系:west999com@outlook.com
特别注意:本站所有转载文章言论不代表本站观点,本站所提供的摄影照片,插画,设计作品,如需使用,请与原作者联系,版权归原作者所有
上一篇:指针的使用
下一篇:2594 解药还是毒药
- 一个工业级、跨平台、轻量级的 tcp 网络服务框架:gevent 2020-06-05
- C++冒泡排序 (基于函数模板实现) 2020-05-31
- C++ 模板类vector 2020-05-31
- C++ 模板类array 2020-05-31
- C++ 模板类vector 2020-05-30
IDC资讯: 主机资讯 注册资讯 托管资讯 vps资讯 网站建设
网站运营: 建站经验 策划盈利 搜索优化 网站推广 免费资源
网络编程: Asp.Net编程 Asp编程 Php编程 Xml编程 Access Mssql Mysql 其它
服务器技术: Web服务器 Ftp服务器 Mail服务器 Dns服务器 安全防护
软件技巧: 其它软件 Word Excel Powerpoint Ghost Vista QQ空间 QQ FlashGet 迅雷
网页制作: FrontPages Dreamweaver Javascript css photoshop fireworks Flash