傳送門

Assignment Time Limit: 2000/1000 MS (Java/Others)????Memory Limit: 32768/32768 K (Java/Others) Total Submission(s): 1418????Accepted Submission(s): 744 Problem Description Last year a terrible earthquake attacked Sichuan province. About 300,000 PLA soldiers attended the rescue, also ALPCs. Our mission is to solve difficulty problems to optimization the assignment of troops. The assignment is measure by efficiency, which is an integer, and the larger the better. We have N companies of troops and M missions, M>=N. One company can get only one mission. One mission can be assigned to only one company. If company i takes mission j, we can get efficiency Eij.? We have a assignment plan already, and now we want to change some companies’ missions to make the total efficiency larger. And also we want to change as less companies as possible. Input For each test case, the first line contains two numbers N and M. N lines follow. Each contains M integers, representing Eij. The next line contains N integers. The first one represents the mission number that company 1 takes, and so on. 1<=N<=M<=50, 1<Eij<=10000. Your program should process to the end of file. Output For each the case print two integers X and Y. X represents the number of companies whose mission had been changed. Y represents the maximum total efficiency can be increased after changing. Sample Input 3 3 2 1 3 3 2 4 1 26 2 2 1 3 2 3 1 2 3 1 2 3 1 2 Sample Output 2 26 1 2 Source 2009 Multi-University Training Contest 5 - Host by NUDT Recommend gaojie

題意：給定一個二分圖，N個點對應M個點，兩兩之間存在一組關系，每組關系一個權值。題目中了給定了一個匹配方案，現在要求滿足這組關系中的最大的匹配權值在原方案上增長了多少？并且還要求求出在原匹配方案上改變最少多少條邊能夠得到這個最大匹配？

idea:增加原配邊的權值，而且又不會對結果造成影響。這聽起來似乎是不太可能的，但是確實有辦法能夠辦到。首先由于頂點數最多50個，那么給所有的邊都乘上55，然后再給所有的原配邊都加上1，那么此時的原配邊的權值相比其他邊更大了，又因為我們最后求解最大權值匹配時是對結果除上55，原配邊匹配再多的數量對這個結果也是于事無補，所有最后MaxValue / 55就是匹配的最大權值，而MaxValue % 55就是能夠保持的最大原配邊數。轉自此處

#include <cmath> #include <cstdio> #include <cstdlib> #include <cstring> #include <iostream> #include <algorithm> using namespace std;#define pi acos(-1) #define endl '\n' #define srand() srand(time(0)); #define me(x,y) memset(x,y,sizeof(x)); #define foreach(it,a) for(__typeof((a).begin()) it=(a).begin();it!=(a).end();it++) #define close() ios::sync_with_stdio(0); cin.tie(0); #define FOR(x,n,i) for(int i=x;i<=n;i++) #define FOr(x,n,i) for(int i=x;i<n;i++) #define W while #define sgn(x) ((x) < 0 ? -1 : (x) > 0) #define bug printf("***********\n"); typedef long long LL; const int INF=0x3f3f3f3f; const LL LINF=0x3f3f3f3f3f3f3f3fLL; const int dx[]={-1,0,1,0,1,-1,-1,1}; const int dy[]={0,1,0,-1,-1,1,-1,1}; const int maxn=1e3+100; const int maxx=1e7+100; const double EPS=1e-7; const int MOD=10000007; #define mod(x) ((x)%MOD); template<class T>inline T min(T a,T b,T c) { return min(min(a,b),c);} template<class T>inline T max(T a,T b,T c) { return max(max(a,b),c);} template<class T>inline T min(T a,T b,T c,T d) { return min(min(a,b),min(c,d));} template<class T>inline T max(T a,T b,T c,T d) { return max(max(a,b),max(c,d));} inline int Scan() {int Res=0,ch,Flag=0;if((ch=getchar())=='-')Flag=1;else if(ch>='0' && ch<='9')Res=ch-'0';while((ch=getchar())>='0'&&ch<='9')Res=Res*10+ch-'0';return Flag ? -Res : Res; } //freopen( "in.txt" , "r" , stdin ); //freopen( "data.out" , "w" , stdout ); //cerr << "run time is " << clock() << endl;int g[maxn][maxn]; //二分圖表示. int link[maxn],lx[maxn],ly[maxn]; //y的匹配關系. x,y的標桿狀態. bool visx[maxn],visy[maxn]; int nx,ny,d; //兩邊的點數. 以及需要尋找的最小的d. bool Find(int x) {visx[x] = true;for(int i=1;i<=ny;i++){if(visy[i]) continue;int tmp = lx[x] + ly[i] - g[x][i];if(!tmp){ //tmp=0表示在當前圖匹配了的邊, 即看現在匹配是否合理,visy[i] = true;if(link[i] == -1 || Find(link[i])){link[i] = x;return true;}}else d=min(d,tmp); //就是在S集合中的x,和不在T集合中的y找一個最小的d.}return false; }int KM() {me(link,-1);me(ly,0); me(lx,0);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];}}for(int i =1 ; i<= nx;i++){while(1){me(visx,false);me(visy,false);d = INF;if(Find(i)) break;//若成功（找到了增廣軌），則該點增廣完成，進入下一個點的增廣//若失敗（沒有找到增廣軌），則需要改變一些點的標號，使得圖中可行邊的數量增加。//方法為：將所有在增廣軌中（就是在增廣過程中遍歷到）的X方點的標號全部減去一個常數d，//所有在增廣軌中的Y方點的標號全部加上一個常數dif(d == INF) return -1; //如果可以確定左邊的點都會被匹配完,則就可以不用加這條語//句. 如果不能就要加上這句話. (所以一般在題目中給了一定完美匹配的話,就可以不用這句話)//而有些題目會問你是否是完美匹配,不是的話輸出-1,是的話在輸出答案,所以這個時候就要加上這句話.//大多數題目是可以不用加的.for(int j = 1 ; j<=nx ; j++)if(visx[j]) lx[j] -= d;for(int j = 1 ; j<=ny ; j++)if(visy[j]) ly[j] += d;}}int res = 0;for(int i=1;i<=ny;i++){if(link[i] != -1) //這些都根據題意來加.res += g[link[i]][i];}cout<<nx-res%55<<" ";return res; } //這道題是保證了一定有最大二分匹配的!!! 所以一些東西可以去掉. void solve() {int n,m;while(~scanf("%d%d",&n,&m)){me(g,0); //找最大所以初始化為較小的值. 這樣一減就會很小了.for(int i=1;i<=n;i++)for(int j=1;j<=m;j++){scanf("%d",&g[i][j]);g[i][j]*=55;}int res1=0;nx=n;ny=m;for(int i=1;i<=nx;i++){int u;scanf("%d",&u);res1+=g[i][u];g[i][u]++;}int res = KM();printf("%d\n",(res-res1)/55);} } int main() {solve(); }

總結

以上是生活随笔為你收集整理的KM匹配 hdu2853（模版的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。