TourTime Limit: 3000/1000 MS (Java/Others) Memory Limit: 65535/65535 K (Java/Others) Problem DescriptionIn the kingdom of Henryy, there are N (2 <= N <= 200) cities, with M (M <= 30000) one-way roads connecting them. You are lucky enough to have a chance to have a tour in the kingdom. The route should be designed as: The route should contain one or more loops. |
————————————————————————————————
题目的意思是是给出一张有向图,要选择几条边使得每个点都落在一个环上,使得所选的边和最小
思路:每个点落在环上,所以每个点的入度出度均为1,这正好符合二分图性质,建立二分图,求最大权匹配,题目要求最小,权值取负数即可
#include <iostream>
#include <cstdio>
#include <string>
#include <cstring>
#include <cmath>
#include <algorithm>
#include <queue>
#include <vector>
#include <set>
#include <stack>
#include <map>
#include <climits>
using namespace std;#define LL long longconst int MAXN = 505;
const int INF = 0x3f3f3f3f;
int g[MAXN][MAXN];
int lx[MAXN],ly[MAXN]; //顶标
int linky[MAXN];
int visx[MAXN],visy[MAXN];
int slack[MAXN];
int nx,ny;
bool find(int x)
{
visx[x] = true;
for(int y = 0; y < ny; y++)
{
if(visy[y])
continue;
int t = lx[x] + ly[y] - g[x][y];
if(t==0)
{
visy[y] = true;
if(linky[y]==-1 || find(linky[y]))
{
linky[y] = x;
return true; //找到增广轨
}
}
else if(slack[y] > t)
slack[y] = t;
}
return false; //没有找到增广轨(说明顶点x没有对应的匹配,与完备匹配(相等子图的完备匹配)不符)
}int KM() //返回最优匹配的值
{
int i,j;
memset(linky,-1,sizeof(linky));
memset(ly,0,sizeof(ly));
for(i = 0; i < nx; i++)
for(j = 0,lx[i] = -INF; j < ny; j++)
lx[i] = max(lx[i],g[i][j]);
for(int x = 0; x < nx; x++)
{
for(i = 0; i < ny; i++)
slack[i] = INF;
while(true)
{
memset(visx,0,sizeof(visx));
memset(visy,0,sizeof(visy));
if(find(x)) //找到增广轨,退出
break;
int d = INF;
for(i = 0; i < ny; i++) //没找到,对l做调整(这会增加相等子图的边),重新找
{
if(!visy[i] && d > slack[i])
d = slack[i];
}
for(i = 0; i < nx; i++)
{
if(visx[i])
lx[i] -= d;
}
for(i = 0; i < ny; i++)
{
if(visy[i])
ly[i] += d;
else
slack[i] -= d;
}
}
}
int result = 0;
for(i = 0; i < ny; i++)
if(linky[i]>-1)
result += g[linky[i]][i];
return -result;
}int main()
{
int n,m,u,v,c,T;
scanf("%d",&T);
while(T--)
{
scanf("%d%d",&n,&m);
nx=ny=n;
memset(g,-INF,sizeof g);
for(int i=0; i<m; i++)
{
scanf("%d%d%d",&u,&v,&c);
u--,v--;
g[u][v]=max(g[u][v],-c);
}
printf("%d\n",KM());
}
return 0;
}