二分图最大权匹配费用流&KM-白红宇

二分图最大权匹配费用流&KM

阅读量：6341 次

发布时间：2019-06-22

本文共 5075 字，大约阅读时间需要 16 分钟。

费用流建图时额外添加一个点A（左->A:(1,0) A->T:(inf,0)）来保证满流边少点多较快边多的情况下表现很差

1 #include
      
         2 #include
       
         3 #include
        
          4 #include
         
           5 #include
          
            6 #include
           
             7 #include
            
              8 #include
             
               9 #define inf (1ll<<(61ll))10 #define l(a) ((a)<<1)11 #define r(a) ((a)<<1|1)12 #define b(a) (1<<(a))13 #define rep(i,a,b) for(int i=a;i<=(b);i++)14 #define clr(a) memset(a,0,sizeof(a))15 typedef long long ll;16 using namespace std;17 int readint(){18 int t=0,f=1;char c=getchar();19 while(!isdigit(c)){20 if(c=='-') f=-1;21 c=getchar();22 }23 while(isdigit(c)){24 t=(t<<3)+(t<<1)+c-'0';25 c=getchar();26 }27 return t*f;28 }29 const int maxn=1009,maxe=400009;30 int n,m,en,S,A,T;31 ll d[maxn];32 ll ans;33 struct edge{34 ll v,w,c;35 edge*next,*r;36 }E[maxe],*pt=E,*fir[maxn],*cur[maxn],*rev[maxn];37 void add(int u,int v,int w,int c){38 pt->v=v;pt->w=w;pt->c=c;39 pt->next=fir[u];fir[u]=pt++;40 }41 void addedge(int u,int v,int w,int c){42 add(u,v,w,c);add(v,u,0,-c);43 fir[u]->r=fir[v];fir[v]->r=fir[u];44 }45 bool p[maxn];46 ll spfa(){47 queue
              
               Q;clr(p);48 rep(i,S,T) d[i]=-inf;49 Q.push(S);p[S]=1;d[S]=0;50 while(!Q.empty()){51 int x=Q.front();Q.pop();p[x]=0;52 for(edge*e=fir[x];e;e=e->next) if(e->w){53 if(d[e->v]
               
                c){54 d[e->v]=d[x]+e->c;55 rev[e->v]=e;56 if(!p[e->v]){57 Q.push(e->v);p[e->v]=1;58 }59 }60 }61 }62 if(d[T]==-inf) return 0;63 for(edge*e=rev[T];e;e=rev[e->r->v]){64 e->w-=1;e->r->w+=1;65 }66 return d[T];67 }68 void Cal(){69 ll t;70 while(t=spfa()) ans+=t;71 }72 int main(){73 //freopen("#input.txt","r",stdin);74 //freopen("#output.txt","w",stdout);75 n=readint();m=readint();en=readint();S=0;A=n+m+1;T=A+1;76 rep(i,1,en){77 int U=readint(),V=readint(),C=readint();78 addedge(U,n+V,1,C);79 }80 rep(i,1,n) addedge(S,i,1,0);81 rep(i,1,m) addedge(n+i,T,1,0);82 rep(i,1,n) addedge(i,A,1,0);addedge(A,T,1000009,0);83 Cal();84 cout<
                
                 <
                 
                  next){88 if(!e->w&&e->v!=A&&e->v!=S) f=e->v-n;89 }90 printf("%d",f);putchar(i==n?'\n':' ');91 }92 //fclose(stdin);93 //fclose(stdout);94 return 0;95 }

费用流

km 调了一个下午半个晚上你敢信？先写了一个貌似n^3的n^4 后来膜着tle的代码写出正确n^3 有空再重新复习敲一下

1 #include
      
          2 #include
       
          3 #include
        
           4 #include
         
            5 #include
          
             6 #include
           
             7 #include
            
              8 #include
             
               9 #define inf (0x7fffffffll) 10 #define l(a) ((a)<<1) 11 #define r(a) ((a)<<1|1) 12 #define b(a) (1<<(a)) 13 #define rep(i,a,b) for(int i=a;i<=(b);i++) 14 #define clr(a) memset(a,0,sizeof(a)) 15 typedef long long ll; 16 typedef unsigned long long ull; 17 using namespace std; 18 int readint(){ 19 int t=0,f=1;char c=getchar(); 20 while(!isdigit(c)){ 21 if(c=='-') f=-1; 22 c=getchar(); 23 } 24 while(isdigit(c)){ 25 t=(t<<3)+(t<<1)+c-'0'; 26 c=getchar(); 27 } 28 return t*f; 29 } 30 const int maxn=509; 31 int n,m,en,now,lp[maxn],rp[maxn],pre[maxn],ld[maxn],rd[maxn],a[maxn],w[maxn][maxn],lc[maxn],rc[maxn];; 32 ll ans; 33 queue
              
               Q; 34 bool Bfs(){ 35 while(!Q.empty()){ 36 int u=Q.front();Q.pop(); 37 rep(v,1,m) if(rc[v]!=now){ 38 int t=ld[u]+rd[v]-w[u][v]; 39 if(!t){ 40 pre[v]=u; 41 if(!rp[v]){ 42 int V=v,tmp; 43 for(int U=u;V;U=pre[V]){ 44 tmp=lp[U];lp[U]=V;rp[V]=U;V=tmp; 45 } 46 return 1; 47 } 48 rc[v]=now; 49 if(lc[rp[v]]!=now){ 50 lc[rp[v]]=now;Q.push(rp[v]); 51 } 52 }else if(t

KM算法

1 #include
      
          2 #include
       
          3 #include
        
           4 #include
         
            5 #include
          
             6 #include
           
             7 #include
            
              8 #include
             
               9 #define inf (0x7fffffff) 10 #define l(a) ((a)<<1) 11 #define r(a) ((a)<<1|1) 12 #define b(a) (1<<(a)) 13 #define rep(i,a,b) for(int i=a;i<=(b);i++) 14 #define clr(a) memset(a,0,sizeof(a)) 15 typedef long long ll; 16 typedef unsigned long long ull; 17 using namespace std; 18 int readint(){ 19 int t=0,f=1;char c=getchar(); 20 while(!isdigit(c)){ 21 if(c=='-') f=-1; 22 c=getchar(); 23 } 24 while(isdigit(c)){ 25 t=(t<<3)+(t<<1)+c-'0'; 26 c=getchar(); 27 } 28 return t*f; 29 } 30 const int maxn=509; 31 int n,m,en,now,pre[maxn],ld[maxn],rd[maxn],lc[maxn],rc[maxn],lp[maxn],rp[maxn],a[maxn],w[maxn][maxn]; 32 queue
              
               Q; 33 bool Bfs(){ 34 while(!Q.empty()){ 35 int u=Q.front();Q.pop(); 36 rep(v,1,m) if(rc[v]!=now){ 37 int t=ld[u]+rd[v]-w[u][v];//u,v不能写错 38 if(!t){ 39 pre[v]=u; 40 if(!rp[v]){ 41 rp[v]=u; 42 int V=v,tmp; 43 for(int U=u;V;U=pre[V]){ 44 tmp=lp[U];lp[U]=V;rp[V]=U;V=tmp; 45 } 46 return 1; 47 } 48 rc[v]=now;//注意 49 if(lc[rp[v]]!=now){ 50 lc[rp[v]]=now;Q.push(rp[v]); 51 } 52 }else if(a[v]>t){ 53 a[v]=t;pre[v]=u; 54 } 55 } 56 } 57 return 0; 58 } 59 void KM(){ 60 rep(S,1,n){ 61 while(!Q.empty()) Q.pop(); 62 rep(i,1,m) a[i]=inf;clr(pre); 63 Q.push(S);lc[S]=++now; 64 for(;;){ 65 bool flag=0; 66 if(Bfs()) break; 67 int del=inf; 68 rep(i,1,m) if(rc[i]!=now) del=min(del,a[i]); 69 rep(i,1,n) if(lc[i]==now) ld[i]-=del; 70 rep(i,1,m) if(rc[i]==now) rd[i]+=del;else if(a[i]