- //EK 算法
- #include <iostream>
- #include <cstdio>
- #include <algorithm>
- #include <queue>
- using namespace std;
- const int N = 210,INF = (int)1e9;
- int n,m,tot;
- int head[N],pre[N],res[N];
- queue<int> que;
- struct node{
- int to,w,nxt;
- }e[N <<1];
- inline void init(){
- while(!que.empty()) que.pop();
- for(int i = 1; i <= n; ++i) res[i] = 0;
- }
- inline void add(int u,int v,int w){
- e[tot].to = v; e[tot].w = w; e[tot].nxt = head[u]; head[u] = tot++;
- }
- bool bfs(int s,int t){
- init();
- pre[s] = -1;
- res[s] = INF;
- que.push(s);
- int now,to;
- while(!que.empty()){
- now = que.front(); que.pop();
- for(int o = head[now]; ~o; o = e[o].nxt){
- to = e[o].to;
- if(!res[to] && e[o].w){
- pre[to] = o;
- res[to] = min(e[o].w, res[now]);
- if(to == t) return true;
- que.push(to);
- }
- }
- }
- return false;
- }
- int EK(int s,int t){
- int ans = 0;
- while(bfs(s,t)){
- for(int o = pre[t]; ~o; o = pre[e[o^1].to]){
- e[o].w -= res[t];
- e[o^1].w += res[t];
- }
- ans += res[t];
- }
- return ans;
- }
- int main(){
- int u,v,w;
- while(~scanf("%d%d",&m,&n)){
- for(int i = 1; i <= n; ++i) head[i] = -1; tot = 0;
- for(int i = 1; i <= m; ++i){
- scanf("%d%d%d",&u,&v,&w);
- add(u,v,w); add(v,u,0);
- }
- printf("%d\n",EK(1,n));
- }
- return 0;
- }
- //Dinic 算法
- #include <iostream>
- #include <cstdio>
- #include <algorithm>
- #include <queue>
- using namespace std;
- const int N = 10010,M = 100010,inf = (int)1e9;
- int n,m,s,t,tot;
- int head[N],lev[N];
- queue<int> que;
- struct node{
- int to,w,nxt;
- }e[M<<1];
- inline void add(int u,int v,int w){
- e[tot].to = v; e[tot].w = w; e[tot].nxt = head[u]; head[u] = tot++;
- }
- inline void init(){
- while(!que.empty()) que.pop();
- for(int i = 1; i <= n; ++i) lev[i] = 0;
- }
- bool bfs(int s,int t){
- lev[s] = 1;
- que.push(s);
- int now,to;
- while(!que.empty()){
- now = que.front(); que.pop();
- if(now == t) return true;
- for(int o = head[now]; ~o; o = e[o].nxt){
- to = e[o].to;
- if(!lev[to] && e[o].w){
- lev[to] = lev[now] + 1;
- que.push(to);
- }
- }
- }
- return false;
- }
- int dfs(int now,int flow,int t){
- if(now == t) return flow;
- int to,sum = 0,tmp;
- for(int o = head[now]; ~o; o = e[o].nxt){
- to = e[o].to;
- if(e[o].w && lev[now] == lev[to] - 1){
- tmp = dfs(to,min(flow - sum, e[o].w),t);
- e[o].w -= tmp; e[o^1].w += tmp;
- if((sum += tmp) == flow) return sum;
- }
- }
- return sum;
- }
- int main(){
- int u,v,w;
- scanf("%d%d%d%d",&n,&m,&s,&t);
- for(int i = 1; i <= n; ++i) head[i] = -1;
- for(int i = 1; i <= m; ++i){
- scanf("%d%d%d",&u,&v,&w);
- add(u,v,w); add(v,u,0);
- }
- int ans = 0;
- while(bfs(s,t)){
- ans += dfs(s,inf,t);
- init();
- }
- printf("%d\n",ans);
- return 0;
- }
来源: http://www.bubuko.com/infodetail-3395266.html