//hdu2853 //二分圖的最大權(quán)匹配，圖中有一些邊，在等權(quán)值的條件下有優(yōu)先選擇權(quán)。 //因?yàn)槭沁xn個(gè)進(jìn)行匹配，我們將每條邊的權(quán)值擴(kuò)大（n+1）倍，這樣每條邊相對(duì)大小是一樣的 //對(duì)于有優(yōu)先選擇權(quán)的邊，我們將這些邊的權(quán)值加一，這樣權(quán)值大的優(yōu)先，但是加1的結(jié)果不會(huì)大于n //最后除以n就可以把這部分忽略掉。答案對(duì)n取模得出的就是我們選擇有優(yōu)先選擇權(quán)邊的數(shù)量。 #include<cstdio> #include<cstring> #include<cstdlib> #include<algorithm> #include<iostream> using namespace std; #define clr(a) memset(a,0,sizeof(a)); const int N=500; const int INF=1<<28; int G[500][500];struct KM{int lx[N],ly[N];//頂標(biāo)int visx[N],visy[N];int line[N];int we[N];//已配對(duì)所對(duì)應(yīng)邊權(quán)值int nx,ny;int slack;bool find(int u){visx[u]=true;for(int v=1;v<=ny;v++){if(!visy[v])//v不在相等子圖中{int t=lx[u]+ly[v]-G[u][v];if(t==0){visy[v]=1;if(line[v]==-1||find(line[v])){line[v]=u;we[v]=G[u][v];return 1;}}else if(t<slack)slack=t;}}return 0;}bool km(){//返回是否完備匹配clr(lx);clr(ly);//memset(lx, -INF, sizeof(lx));//memset(ly, -INF, sizeof(ly));memset(line,-1,sizeof(line));for(int i=1;i<=nx;i++){for(int j=1;j<=ny;j++){if(G[i][j]>lx[i])lx[i]=G[i][j];//初始化為xi所連接的最大權(quán)值}}for(int u=1;u<=nx;u++){while(true){slack=INF;clr(visx);clr(visy);if(find(u))break;if(slack==INF)return 0;for(int i=1;i<=nx;i++){if(visx[i])lx[i]-=slack;}for(int i=1;i<=ny;i++){if(visy[i])ly[i]+=slack;}}}return 1;}int best_match(){int res=0;km();for(int u=1;u<=ny;u++){if(line[u]==-1)continue;res+=we[u];}return res;} }kk;int main(){int n,m,u;while(scanf("%d%d",&n,&m)!=EOF){clr(G);for(int i=1;i<=n;i++){for(int j=1;j<=m;j++){scanf("%d",&u);G[i][j]=u*(n+1);}}int sum=0;for(int i=1;i<=n;i++){scanf("%d",&u);sum+=G[i][u]/(n+1);G[i][u]++;}kk.nx=n,kk.ny=m;int ans=kk.best_match();printf("%d %d\n",n-ans%(n+1),(ans/(n+1))-sum);}return 0; }

總結(jié)

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

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