ISAP

跑的是比Dinic快辣。

更新：指针版。。。。

 #include<iostream>

 #include<cstdio>

 #include<cmath>

 #include<algorithm>

 #include<queue>

 #include<cstring>

 #define PAU putchar(' ')

 #define ENT putchar('\n')

 using namespace std;

 const int maxn=+,maxm=+,inf=-1u>>;

 struct ISAP{

     struct ted{int x,y,w;ted*nxt,*re;}adj[maxm],*fch[maxn],*cur[maxn],*ret[maxn],*ms;

     int gap[maxn],d[maxn],S,T,n;

     void init(int n){

         this->n=n;ms=adj;memset(d,-,sizeof(d));return;

     }

     void ade(int u,int v,int w){

         *ms=(ted){u,v,w,fch[u],ms+};fch[u]=ms++;

         *ms=(ted){v,u,,fch[v],ms-};fch[v]=ms++;

         return;

     }

     void bfs(){

         queue<int>Q;Q.push(T);d[T]=;

         while(!Q.empty()){

             int u=Q.front();Q.pop();

             for(ted*e=fch[u];e;e=e->nxt){

                 int v=e->y;if(d[v]<) d[v]=d[u]+,Q.push(v);

             }

         } return;

     }

     int flow(int S,int T){

         int k=S,flow=;ted*e;

         for(int i=;i<=n;i++) cur[i]=fch[i];

         while(d[S]<n){

             if(k==T){

                 int mi=inf;

                 for(int i=S;i!=T;i=cur[i]->y) if(cur[i]->w<mi) mi=cur[i]->w;

                 for(int i=S;i!=T;i=cur[i]->y) cur[i]->w-=mi,cur[i]->re->w+=mi;

                 flow+=mi;k=S;

             }

             for(e=cur[k];e;e=e->nxt) if(e->w>&&d[k]==d[e->y]+) break;

             if(e) cur[k]=e,ret[e->y]=e->re,k=e->y;

             else{

                 if(--gap[d[k]]==) break;cur[k]=fch[k];int lim=n;

                 for(ted*e=fch[k];e;e=e->nxt) if(e->w&&d[e->y]<lim) lim=d[e->y];

                 d[k]=lim+;gap[d[k]]++;if(k!=S) k=ret[k]->y;

             }

         } return flow;

     }

 }sol;

 inline int read(){

     int x=,sig=;char ch=getchar();

     while(!isdigit(ch)){if(ch=='-')sig=-;ch=getchar();}

     while(isdigit(ch))x=*x+ch-'',ch=getchar();

     return x*=sig;

 }

 inline void write(int x){

     if(x==){putchar('');return;}if(x<)putchar('-'),x=-x;

     int len=,buf[];while(x)buf[len++]=x%,x/=;

     for(int i=len-;i>=;i--)putchar(buf[i]+'');return;

 }

 int n,m;

 void init(){

     n=read();m=read();sol.init(n);

     int x,y,w;

     while(m--) x=read(),y=read(),w=read(),sol.ade(x,y,w);

     write(sol.flow(,n));

     return;

 }

 void work(){

     return;

 }

 void print(){

     return;

 }

 int main(){init();work();print();return ;}

数组版：

 #include<iostream>

 #include<cstdio>

 #include<cmath>

 #include<algorithm>

 #include<queue>

 #include<cstring>

 #define PAU putchar(' ')

 #define ENT putchar('\n')

 using namespace std;

 const int maxn=+,maxm=+,inf=-1u>>;

 struct ISAP{

     struct tedge{int x,y,w,next;}adj[maxm];int ms,fch[maxn];

     int gap[maxn],s[maxn],cur[maxn],d[maxn],S,T,top,n;

     void init(int n){

         this->n=n;ms=;top=;

         memset(fch,-,sizeof(fch));

         memset(d,-,sizeof(d));

         return;

     }

     void addedge(int w,int v,int u){

         adj[ms]=(tedge){u,v,w,fch[u]};fch[u]=ms++;

         adj[ms]=(tedge){v,u,,fch[v]};fch[v]=ms++;

         return;

     }

     void bfs(){

         queue<int>Q;Q.push(T);d[T]=;

         while(!Q.empty()){

             int u=Q.front();Q.pop();

             for(int i=fch[u];i!=-;i=adj[i].next){

                 int v=adj[i].y;

                 if(d[v]==-) d[v]=d[u]+,Q.push(v);

             }

         } return;

     }

     int maxflow(int S,int T){

         this->S=S;this->T=T;bfs();int k=S,i,flow=;

         for(i=;i<=n;i++) cur[i]=fch[i],gap[d[i]]++;

         while(d[S]<n){

             if(k==n){

                 int mi=inf,pos;

                 for(i=;i<top;i++) if(adj[s[i]].w<mi) mi=adj[s[i]].w,pos=i;

                 for(i=;i<top;i++) adj[s[i]].w-=mi,adj[s[i]^].w+=mi;

                 flow+=mi;top=pos;k=adj[s[top]].x;

             }

             for(i=cur[k];i!=-;i=adj[i].next){

                 int v=adj[i].y;

                 if(adj[i].w&&d[k]==d[v]+){cur[k]=i;k=v;s[top++]=i;break;}

             }

             if(i==-){

                 int lim=n;

                 for(i=fch[k];i!=-;i=adj[i].next){

                     int v=adj[i].y;

                     if(adj[i].w&&d[v]<lim) lim=d[v],cur[k]=i;

                 } if(--gap[d[k]]==) break;

                 d[k]=lim+;gap[d[k]]++;

                 if(k!=S) k=adj[s[--top]].x;

             }

         } return flow;

     }

 }sol;

 inline int read(){

     int x=,sig=;char ch=getchar();

     while(!isdigit(ch)){if(ch=='-') sig=-;ch=getchar();}

     while(isdigit(ch)) x=*x+ch-'',ch=getchar();

     return x*=sig;

 }

 inline void write(int x){

     if(x==){putchar('');return;}if(x<) putchar('-'),x=-x;

     int len=,buf[];while(x) buf[len++]=x%,x/=;

     for(int i=len-;i>=;i--) putchar(buf[i]+'');return;

 }

 void init(){

     int n=read(),m=read();sol.init(n);

     while(m--) sol.addedge(read(),read(),read());

     write(sol.maxflow(,n));

     return;

 }

 void work(){

     return;

 }

 void print(){

     return;

 }

 int main(){

     init();work();print();return ;

 }

搜索

复制