當(dāng)前位置：首頁 > 编程资源 > 编程问答 >内容正文

编程问答

UOJ#80 二分图最大权匹配 [模板题]

發(fā)布時(shí)間：2025/1/21 编程问答 60 豆豆

生活随笔收集整理的這篇文章主要介紹了 UOJ#80 二分图最大权匹配 [模板题] 小編覺得挺不錯(cuò)的,現(xiàn)在分享給大家,幫大家做個(gè)參考.

從前一個(gè)和諧的班級(jí)，有?

有若干個(gè)這樣的條件：第?

請(qǐng)問這個(gè)班級(jí)里幸福程度之和最大是多少？

輸入格式

第一行三個(gè)正整數(shù)，

接下來?

輸出格式

第一行一個(gè)整數(shù)，表示幸福程度之和的最大值。

接下來一行?

樣例一

input

2 2 3 1 1 100 1 2 1 2 1 1

output

100 1 0

限制與約定

時(shí)間限制：

空間限制：

二分圖最大權(quán)匹配模板題 KM算法

KM算法略神奇的樣子……

http://www.cnblogs.com/wenruo/p/5264235.html

↑感覺這里講得挺清晰

KM算法求的是最大權(quán)完備匹配，為了解決兩邊點(diǎn)數(shù)不同的情況，需要虛擬一些點(diǎn)使得兩邊點(diǎn)數(shù)相等

↑但是這種DFS寫法被無情卡掉

1 /*by SilverN*/ 2 #include<algorithm> 3 #include<iostream> 4 #include<cstring> 5 #include<cstdio> 6 #include<cmath> 7 #include<vector> 8 #define LL long long 9 using namespace std; 10 const LL INF=1LL<<62; 11 const int mxn=411; 12 int read(){ 13 int x=0,f=1;char ch=getchar(); 14 while(ch<'0' || ch>'9'){if(ch=='-')f=-1;ch=getchar();} 15 while(ch>='0' && ch<='9'){x=x*10+ch-'0';ch=getchar();} 16 return x*f; 17 } 18 void write(LL x){ 19 if(x>9)write(x/10); 20 putchar(x%10+'0'); 21 return; 22 } 23 inline LL mini(LL a,LL b){return a<b?a:b;} 24 inline LL maxi(LL a,LL b){return a>b?a:b;} 25 int nL,nR,bl,br,m; 26 int visL[mxn],visR[mxn]; 27 LL exL[mxn],exR[mxn]; 28 int link[mxn]; 29 LL slack[mxn]; 30 int mp[mxn][mxn]; 31 LL ans=0; 32 int a[mxn]; 33 int dtime=0; 34 bool DFS(int u){ 35 visL[u]=dtime; 36 for(int i=1;i<=nR;i++){ 37 if(visR[i]==dtime)continue; 38 LL d=exL[u]+exR[i]-mp[u][i]; 39 if(!d){ 40 visR[i]=dtime; 41 if(!link[i] || DFS(link[i])){ 42 link[i]=u; 43 return 1; 44 } 45 } 46 else slack[i]=min(slack[i],d); 47 } 48 return 0; 49 } 50 void KM(){ 51 // memset(link,0,sizeof link); 52 // memset(exR,0,sizeof exR); 53 for(int i=1;i<=nL;i++){ 54 exL[i]=0; 55 for(int j=1;j<=nR;j++){ 56 exL[i]=maxi(exL[i],mp[i][j]); 57 } 58 } 59 for(int i=1;i<=nL;i++){ 60 // memset(slack,0x3f,sizeof slack); 61 for(int j=1;j<=nR;j++)slack[j]=INF; 62 while(1){//直到匹配成功為止 63 dtime++; 64 // memset(visL,0,sizeof visL); 65 // memset(visR,0,sizeof visR); 66 if(DFS(i))break; 67 LL d=INF; 68 for(int j=1;j<=nR;j++){ 69 if(visR[j]!=dtime)d=mini(d,slack[j]); 70 } 71 for(int j=1;j<=nL;j++){ 72 if(visL[j]==dtime)exL[j]-=d; 73 if(visR[j]==dtime)exR[j]+=d; 74 else slack[j]-=d; 75 } 76 } 77 } 78 ans=0; 79 nL=bl;nR=br; 80 for(int i=1;i<=nR;i++){ 81 if(mp[link[i]][i]){ 82 a[link[i]]=i; 83 ans+=mp[link[i]][i]; 84 } 85 } 86 printf("%lld\n",ans); 87 for(int i=1;i<=nL;i++){ 88 write(a[i]); 89 putchar(' '); 90 } 91 printf("\n"); 92 return; 93 } 94 int main(){ 95 int i,j; 96 nL=read(); 97 nR=read(); 98 bl=nL;br=nR; 99 nL=max(nL,nR); 100 nR=nL; 101 m=read(); 102 int u,v,w; 103 for(i=1;i<=m;i++){ 104 u=read();v=read();w=read(); 105 mp[u][v]=w; 106 } 107 KM(); 108 return 0; 109 } DFS TLE

于是在status里抄了個(gè)BFS的寫法。

1 /*by SilverN*/ 2 #include<algorithm> 3 #include<iostream> 4 #include<cstring> 5 #include<cstdio> 6 #include<cmath> 7 #include<vector> 8 #define LL long long 9 using namespace std; 10 const int INF=0x3f3f3f3f; 11 const int mxn=411; 12 int read(){ 13 int x=0,f=1;char ch=getchar(); 14 while(ch<'0' || ch>'9'){if(ch=='-')f=-1;ch=getchar();} 15 while(ch>='0' && ch<='9'){x=x*10+ch-'0';ch=getchar();} 16 return x*f; 17 } 18 void write(LL x){ 19 if(x>9)write(x/10); 20 putchar(x%10+'0'); 21 return; 22 } 23 inline int mini(int a,int b){return a<b?a:b;} 24 inline int maxi(int a,int b){return a>b?a:b;} 25 int nL,nR,bl,br,m; 26 int visL[mxn],visR[mxn]; 27 int exL[mxn],exR[mxn]; 28 int link[mxn],pre[mxn],lx[mxn]; 29 int slack[mxn]; 30 int mp[mxn][mxn]; 31 // 32 LL ans=0; 33 int a[mxn]; 34 int dtime=0; 35 int q[mxn<<1],hd,tl; 36 void Aug(int rt){ 37 if(!rt)return; 38 link[rt]=pre[rt]; 39 Aug(lx[pre[rt]]); 40 lx[pre[rt]]=rt; 41 return; 42 } 43 void BFS(int S){ 44 int i,j,tmp;++dtime; 45 memset(slack,0x3f,sizeof slack); 46 hd=tl=1;q[tl]=S; 47 while(1){ 48 while(hd<=tl){ 49 int u=q[hd];++hd; 50 visL[u]=dtime; 51 for(int i=1;i<=nR;i++){ 52 if(visR[i]^dtime){ 53 tmp=exL[u]+exR[i]-mp[u][i]; 54 if(!tmp){ 55 visR[i]=dtime;pre[i]=u; 56 if(!link[i]){ 57 Aug(i); 58 return; 59 } 60 q[++tl]=link[i]; 61 // 62 } 63 else if(tmp<slack[i])slack[i]=tmp,pre[i]=u; 64 } 65 } 66 } 67 tmp=INF; 68 for(i=1;i<=nR;i++)if(visR[i]^dtime)tmp=mini(tmp,slack[i]); 69 for(i=1;i<=nL;i++){ 70 if(visL[i]==dtime)exL[i]-=tmp; 71 if(visR[i]==dtime)exR[i]+=tmp; 72 else slack[i]-=tmp; 73 } 74 for(i=1;i<=nR;i++){ 75 if(visR[i]^dtime && !slack[i]){ 76 visR[i]=dtime; 77 if(!link[i]){ 78 // link[i]=pre[i]; 79 Aug(i); 80 return; 81 } 82 q[++tl]=link[i]; 83 } 84 } 85 } 86 return; 87 } 88 void KM(){ 89 for(int i=1;i<=nL;i++){ 90 exL[i]=0; 91 for(int j=1;j<=nR;j++) 92 exL[i]=max(exL[i],mp[i][j]); 93 } 94 for(int i=1;i<=nL;i++) BFS(i); 95 ans=0; 96 nL=bl;nR=br; 97 for(int i=1;i<=nR;i++){ 98 if(mp[link[i]][i]){ 99 a[link[i]]=i; 100 ans+=mp[link[i]][i]; 101 } 102 } 103 printf("%lld\n",ans); 104 for(int i=1;i<=nL;i++){ 105 write(a[i]); 106 putchar(' '); 107 } 108 printf("\n"); 109 return; 110 } 111 int main(){ 112 int i,j; 113 nL=read(); 114 nR=read(); 115 bl=nL;br=nR; 116 nL=max(nL,nR); 117 nR=nL; 118 m=read(); 119 int u,v,w; 120 for(i=1;i<=m;i++){ 121 u=read();v=read();w=read(); 122 mp[u][v]=w; 123 } 124 KM(); 125 return 0; 126 }

轉(zhuǎn)載于:https://www.cnblogs.com/SilverNebula/p/6710604.html

總結(jié)

以上是生活随笔為你收集整理的UOJ#80 二分图最大权匹配 [模板题]的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。

上一篇： IOS 输入框 placeholder字
下一篇：安装Orcale 10g SP3时报ou