网络流 KM dinic

study from：

https://blog.csdn.net/A_Comme_Amour/article/details/79356220

Edmonds-Karp 无优化

最坏时间复杂度O(n*m*m) n为点数，m为边数

  1 #include <cstdio>
  2 #include <cstdlib>
  3 #include <cmath>
  4 #include <ctime>
  5 #include <cstring>
  6 #include <string>
  7 #include <map>
  8 #include <set>
  9 #include <list>
 10 #include <queue>
 11 #include <stack>
 12 #include <vector>
 13 #include <bitset>
 14 #include <algorithm>
 15 #include <iostream>
 16 using namespace std;
 17 #define ll long long
 18 const int maxn=1e4+10;
 19 const int inf=1e9;
 20 
 21 struct node
 22 {
 23     int d,len;
 24     node *next,*opp;
 25 }*e[maxn],*pre[maxn];
 26 
 27 int sum=0,s,t,add[maxn];
 28 queue<int> st;
 29 bool vis[maxn];
 30 
 31 void add_edge(int x,int y,int len)
 32 {
 33     node *p1=(node*) malloc (sizeof(node));
 34     node *p2=(node*) malloc (sizeof(node));
 35 
 36     p1->d=y;
 37     p1->len=len;
 38     p1->next=e[x];
 39     p1->opp=p2;
 40     e[x]=p1;
 41 
 42     p2->d=x;///注意
 43     p2->len=0;///注意
 44     p2->next=e[y];
 45     p2->opp=p1;
 46     e[y]=p2;
 47 }
 48 
 49 void bfs()
 50 {
 51     int d,dd,v;
 52     node *p;
 53     while (1)
 54     {
 55         memset(add,0,sizeof(add));
 56         ///vis不用初始化
 57         add[s]=inf;
 58         vis[s]=1;
 59         st.push(s);
 60         while (!st.empty())
 61         {
 62             d=st.front();
 63             st.pop();
 64             p=e[d];
 65             while (p)
 66             {
 67                 dd=p->d;
 68                 v=min(add[d],p->len);
 69                 if (add[dd]<v)
 70                 {
 71                     add[dd]=v;
 72                     pre[dd]=p->opp;
 73                     if (!vis[dd])
 74                     {
 75                         vis[dd]=1;
 76                         st.push(dd);
 77                     }
 78                 }
 79                 p=p->next;
 80             }
 81             vis[d]=0;
 82         }
 83 
 84         if (add[t]==0)
 85             break;
 86 
 87         sum+=add[t];
 88         d=t;
 89         while (d!=s)
 90         {
 91             pre[d]->len+=add[t];
 92             pre[d]->opp->len-=add[t];
 93             d=pre[d]->d;
 94         }
 95     }
 96 }
 97 
 98 int main()
 99 {
100     int n,m,x,y,z;
101     scanf("%d%d%d%d",&n,&m,&s,&t);
102     while (m--)
103     {
104         scanf("%d%d%d",&x,&y,&z);
105         add_edge(x,y,z);
106     }
107     bfs();
108     printf("%d",sum);
109     return 0;
110 }

study from https://www.luogu.org/problemnew/solution/P3376 第一个题解的dinic

dinic

  1 #include <cstdio>
  2 #include <cstdlib>
  3 #include <cmath>
  4 #include <ctime>
  5 #include <cstring>
  6 #include <string>
  7 #include <map>
  8 #include <set>
  9 #include <list>
 10 #include <queue>
 11 #include <stack>
 12 #include <vector>
 13 #include <bitset>
 14 #include <algorithm>
 15 #include <iostream>
 16 using namespace std;
 17 #define ll long long
 18 const int maxn=1e4+10;
 19 const int inf=1e9;
 20 
 21 struct node
 22 {
 23     int d,len;
 24     node *next,*opp;
 25 }*e[maxn];
 26 
 27 int sum=0,s,t;
 28 int q[maxn],dep[maxn];
 29 bool vis[maxn];
 30 
 31 void add_edge(int x,int y,int len)
 32 {
 33     node *p1=(node*) malloc (sizeof(node));
 34     node *p2=(node*) malloc (sizeof(node));
 35 
 36     p1->d=y;
 37     p1->len=len;
 38     p1->next=e[x];
 39     p1->opp=p2;
 40     e[x]=p1;
 41 
 42     p2->d=x;
 43     p2->len=0;///注意
 44     p2->next=e[y];
 45     p2->opp=p1;
 46     e[y]=p2;
 47 }
 48 
 49 ///前面的网络流算法，每进行一次增广，都要做 一遍BFS，十分浪费。能否少做几次BFS?
 50 
 51 bool bfs()
 52 {
 53     int head=0,tail=1,d,dd;
 54     node *p;
 55     memset(vis,0,sizeof(vis));
 56     vis[s]=1;
 57     dep[s]=1;
 58     q[1]=s;
 59 
 60     while (head<tail)
 61     {
 62         head++;
 63         d=q[head];
 64         p=e[d];
 65         while (p)
 66         {
 67             dd=p->d;
 68             if (p->len>0 && !vis[dd])
 69             {
 70                 tail++;
 71                 q[tail]=dd;
 72                 vis[dd]=1;
 73                 dep[dd]=dep[d]+1;
 74             }
 75             p=p->next;
 76         }
 77     }
 78     if (vis[t])
 79         return 1;
 80     return 0;
 81 }
 82 
 83 ///DFS找到一条增广路径后，并不立即结束，而是回溯后继续DFS寻找下一个增广路径
 84 
 85 int dfs(int d,int add)
 86 {
 87     if (!add || d==t)
 88         return add;
 89     int totf=0,f,dd;
 90     node *p=e[d];
 91     while (p)
 92     {
 93         dd=p->d;
 94         if (dep[dd]==dep[d]+1 && (f=dfs(dd,min(add,p->len)))>0)///注意
 95         {
 96             totf+=f;
 97             add-=f;///注意
 98             p->len-=f;
 99             p->opp->len+=f;
100         }
101         p=p->next;
102     }
103     return totf;
104 }
105 
106 int main()
107 {
108     int n,m,x,y,z;
109     scanf("%d%d%d%d",&n,&m,&s,&t);
110     while (m--)
111     {
112         scanf("%d%d%d",&x,&y,&z);
113         add_edge(x,y,z);
114     }
115     while (bfs())
116         sum+=dfs(s,inf);
117     printf("%d",sum);
118     return 0;
119 }