蓝桥杯算法训练——网络流裸题

时间限制：1.0s 内存限制：256.0MB

问题描述

　　一个有向图，求1到N的最大流

输入格式

　　第一行N M，表示点数与边数
　　接下来M行每行s t c表示一条从s到t的容量为c的边

输出格式

　　一个数最大流量

样例输入

6 10
1 2 4
1 3 8
2 3 4
2 4 4
2 5 1
3 4 2
3 5 2
4 6 7
5 4 6
5 6 3

样例输出

数据约定：

n<=1000 m<=10000

解题报告：

裸题，Dicnic加一下优化——多路增广+炸点优化+当前弧优化，以前没更新过这网络流的模板

 1 #include<bits/stdc++.h>
 2 using namespace std;
 3 const int inf=0x3f3f3f3f;
 4 typedef long long ll;
 5 const int maxn = 1010;
 6 const int maxm = 20010;
 7 struct node {
 8     int v,net;
 9     ll w;
10     node(){}
11     node(int v,int net,ll w):v(v),net(net),w(w){}
12 }e[maxm];
13 int head[maxn],cnt,dis[maxn],n,cur[maxn];
14 bool vis[maxn];
15 void addedge(int u,int v,ll w) {
16     e[cnt]=node(v,head[u],w);
17     head[u]=cnt++;
18     e[cnt]=node(u,head[v],0);
19     head[v]=cnt++;
20 }
21 bool bfs(int st,int ed) {
22     if(st==ed) return false;
23     for(int i=1;i<=n;i++)
24         dis[i]=inf,vis[i]=false;
25     dis[ed]=inf;
26     vis[ed]=false;
27     dis[st]=0;
28     queue<int>que;
29     que.push(st);
30     while(!que.empty()) {
31         int u=que.front();
32         que.pop();
33         vis[u]=false;
34         for(int i=head[u];~i;i=e[i].net) {
35             int v=e[i].v;
36             if(e[i].w>0&&dis[v]>dis[u]+1) {
37                 dis[v]=dis[u]+1;
38                 if(!vis[v]) {
39                     que.push(v);
40                     vis[v]=true;
41                 }
42             }
43         }
44     }
45     return dis[ed]!=inf;
46 }
47 ll dfs(int st,ll maxflow,int ed) { ///maxflow表示当前的源点能流出的最大流 
48     if(st==ed) {
49         return maxflow;
50     }
51     ll res=0;
52     for(int &i=cur[st];~i;i=e[i].net) {    ///没记错的话叫当前弧优化 
53         int v=e[i].v;
54         if(e[i].w>0&&dis[v]==dis[st]+1) {
55             ll f=dfs(v,min(maxflow-res,e[i].w),ed);
56             res+=f;
57             e[i].w-=f;
58             e[i^1].w+=f;
59             if(res==maxflow) return res;
60         }
61     }
62     if(!res) dis[st] = inf;///炸点优化？？ 
63     return res;
64 }
65 ll Dicnic(int st,int ed) {
66     ll maxFlow = 0;
67     while(bfs(st,ed)) {
68         for(int i=1;i<=n;i++)
69             cur[i]=head[i];
70         maxFlow+=dfs(st,inf,ed);
71     }
72     return maxFlow;
73 }
74 int main()
75 {
76     int m;
77     cin>>n>>m;
78     memset(head,-1,sizeof(head));
79     for(int i=1;i<=m;i++) {
80         int u,v;
81         ll w;
82         cin>>u>>v>>w;
83         addedge(u,v,w);
84     }
85     cout<<Dicnic(1,n)<<endl;
86     return 0;
87 }

View Code

蓝桥杯 算法训练——网络流裸题

蓝桥杯算法训练——网络流裸题