本文主要是介绍CSU 1623 Inspectors（二分图最大权匹配 KM算法）（UVAlive 6879），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
题目链接：http://acm.csu.edu.cn/OnlineJudge/problem.php?id=1623
选用一些边 覆盖所有的点 使得这些边的权值和最小
比赛时的想法是用一般图最大权匹配 样例也过了 但是提交总是WA
看kuangbin模版中写的是点的个数必须是偶数。。是不是有可能是这个原因
改用二分图最大权匹配之后就过了。。。。
#include <cstdio>
#include <iostream>
#include <cstring>
#include <cmath>
#include <algorithm>
#include <string.h>
#include <string>
#include <vector>
#include <queue>#define MEM(a,x) memset(a,x,sizeof a)
#define eps 1e-8
#define MOD 10009
#define MAXN 110
#define MAXM 100010
#define INF 99999999
#define ll __int64
#define bug cout<<"here"<<endl
#define fread freopen("ceshi.txt","r",stdin)
#define fwrite freopen("out.txt","w",stdout)using namespace std;int Read()
{char c = getchar();while (c < '0' || c > '9') c = getchar();int x = 0;while (c >= '0' && c <= '9') {x = x * 10 + c - '0';c = getchar();}return x;
}void Print(int a)
{if(a>9)Print(a/10);putchar(a%10+'0');
}int nx,ny;
int g[MAXN][MAXN];
int linker[MAXN],lx[MAXN],ly[MAXN];
int slack[MAXN];
bool visx[MAXN],visy[MAXN];
bool dfs(int x)
{visx[x]=1;for(int y=0;y<ny;y++){if(visy[y]) continue;int tmp=lx[x]+ly[y]-g[x][y];if(tmp==0){visy[y]=1;if(linker[y]==-1||dfs(linker[y])){linker[y]=x;return 1;}}else if(slack[y]>tmp)slack[y]=tmp;}return 0;
}int KM()
{MEM(linker,-1);MEM(ly,0);for(int i=0;i<nx;i++){lx[i]=-INF;for(int j=0;j<ny;j++)if(g[i][j]>lx[i])lx[i]=g[i][j];}for(int x=0;x<nx;x++){for(int i=0;i<ny;i++)slack[i]=INF;while(1){MEM(visx,0);MEM(visy,0);if(dfs(x)) break;int d=INF;for(int i=0;i<ny;i++)if(!visy[i]&&d>slack[i])d=slack[i];for(int i=0;i<nx;i++)if(visx[i])lx[i]-=d;for(int i=0;i<ny;i++){if(visy[i]) ly[i]+=d;else slack[i]-=d;}}}int res=0;for(int i=0;i<ny;i++)if(linker[i]!=-1)res+=g[linker[i]][i];return res;
}int main()
{
// fread;int tc;scanf("%d",&tc);int cs=1;while(tc--){int n;scanf("%d",&n);
// MEM(g,0);for(int i=0;i<n;i++)for(int j=0;j<n;j++)g[i][j]=-INF;//初始值 要为负for(int i=0;i<n-1;i++)for(int j=i+1;j<n;j++){int w;scanf("%d",&w);g[i][j]=g[j][i]=-w;}nx=ny=n;int res=-KM();printf("Case %d: %d\n",cs++,res);}return 0;
}
这篇关于CSU 1623 Inspectors（二分图最大权匹配 KM算法）（UVAlive 6879）的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
