Network flow KM dinic

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

  1 #include <cstdio>
  2 #include <cstdlib>
  3 #include <cmath>
  4 #include <cstring>
  5 #include <time.h>
  6 #include <string>
  7 #include <set>
  8 #include <map>
  9 #include <list>
 10 #include <stack>
 11 #include <queue>
 12 #include <vector>
 13 #include <bitset>
 14 #include <ext/rope>
 15 #include <algorithm>
 16 #include <iostream>
 17 using namespace std;
 18 #define ll long long
 19 #define minv 1e-6
 20 #define inf 1e9
 21 #define pi 3.1415926536
 22 #define nl 2.7182818284
 23 const ll mod=1e9+7;//998244353
 24 const int maxn=1e4+10;
 25 
 26 struct node
 27 {
 28     int d,len;
 29     node *opp;
 30     node *next;
 31 }*e[maxn];
 32 
 33 int n,s,t;
 34 int q[maxn],dep[maxn];
 35 bool vis[maxn];
 36 
 37 bool bfs()
 38 {
 39     node *p;
 40     int head=0,tail=1,d,dd;
 41     memset(vis,0,sizeof(vis));
 42     q[1]=s;
 43     dep[s]=0;
 44     vis[s]=1;
 45     while (head<tail)
 46     {
 47         head++;
 48         d=q[head];
 49         p=e[d];
 50         while (p)
 51         {
 52             dd=p->d;
 53             if (p->len>0 && !vis[dd])
 54             {
 55                 tail++;
 56                 q[tail]=dd;
 57                 vis[dd]=1;
 58                 dep[dd]=dep[d]+1;
 59             }
 60             p=p->next;
 61         }
 62     }
 63     if (dep[t]==0)
 64         return 0;
 65     else
 66         return 1;
 67 }
 68 
 69 int dfs(int d,int add)
 70 {
 71     if (d==t)
 72         return add;
 73     int value,dd;
 74     node *p=e[d];
 75     while (p)
 76     {
 77         dd=p->d;
 78         if (dep[dd]==dep[d]+1 && p->len>0 && !vis[dd])
 79         {
 80             vis[dd]=1;
 81             if ((value=dfs(dd,min(add,p->len)))>0)
 82             {
 83                 p->len-=value;
 84                 p->opp->len+=value;
 85                 return value;
 86             }
 87         }
 88         p=p->next;
 89     }
 90 }
 91 
 92 int main()
 93 {
 94     node *p,*P;
 95     int m,x,y,z,add,sum=0;
 96     scanf("%d%d%d%d",&n,&m,&s,&t);
 97     while (m--)
 98     {
 99         scanf("%d%d%d",&x,&y,&z);
100         p=(node*) malloc (sizeof(node));
101         P=(node*) malloc (sizeof(node));
102 
103         p->d=y;
104         p->len=z;
105         p->opp=P;
106         p->next=e[x];
107         e[x]=p;
108 
109         P->d=x;
110         P->len=0;
111         P->opp=p;
112         P->next=e[y];
113         e[y]=P;
114     }
115     do
116     {
117         if (!bfs())
118             break;
119         memset(vis,0,sizeof(vis));
120         add=dfs(s,inf);
121         sum+=add;
122     }
123     while (add!=0);
124     printf("%d",sum);
125     return 0;
126 }