【题意】
将一个无向图删边得到一些子图，并使每个子图中存在哈密顿回路，并使所有哈密顿回路上边的权值最小
【分析】
形成哈密顿回路的话就是每个点入度出度都为0.拆点建二分图，然后KM。
这题要判断能不能完美匹配，这里修改一下模版！！
INF 那里要判断一下再减delta！！
代码如下：
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<iostream>
#include<algorithm>
#include<queue>
using namespace std;
#define Maxn 1010
#define Maxm 10010
#define INF 0xfffffff struct node
{
int x,y,c,next;
}t[Maxm*];int len;
int first[Maxn]; void ins(int x,int y,int c)
{
t[++len].x=x;t[len].y=y;t[len].c=-c;
t[len].next=first[x];first[x]=len;
} int mymin(int x,int y) {return x<y?x:y;}
int mymax(int x,int y) {return x>y?x:y;} int lx[Maxn],ly[Maxn];
int slack[Maxn],match[Maxn];
bool visx[Maxn],visy[Maxn];
int n; bool ffind(int x)
{
visx[x]=;
for(int i=first[x];i;i=t[i].next) if(!visy[t[i].y])
{
int y=t[i].y;
if(t[i].c==lx[x]+ly[y])
{
visy[y]=;
if(!match[y]||ffind(match[y]))
{
match[y]=x;
return ;
}
}
else slack[y]=mymin(slack[y],lx[x]+ly[y]-t[i].c);
}
return ; } bool solve()
{
memset(match,,sizeof(match));
memset(ly,,sizeof(ly));
for(int i=;i<=n;i++)
{
lx[i]=-INF;
// printf("%d\n",i);
for(int j=first[i];j;j=t[j].next)
{
// printf("%d\n",j);
lx[i]=mymax(lx[i],t[j].c); }
}
int i;
for(i=;i<=n;i++)
{
for(int j=;j<=n;j++) slack[j]=INF;
while()
{
memset(visx,,sizeof(visx));
memset(visy,,sizeof(visy));
if(ffind(i)) break;
int delta=INF;
for(int j=;j<=n;j++) if(!visy[j])
delta=mymin(delta,slack[j]);
if(delta==INF) return ;
for(int j=;j<=n;j++)
{
if(visx[j]) lx[j]-=delta;
if(visy[j]) ly[j]+=delta;
else if(slack[j]!=INF) slack[j]-=delta;
}
}
}
return ;
} int main()
{
int T,kase=;
scanf("%d",&T);
while(T--)
{
int m;
scanf("%d%d",&n,&m);
len=;
memset(first,,sizeof(first));
for(int i=;i<=m;i++)
{
int x,y,c;
scanf("%d%d%d",&x,&y,&c);
ins(x,y,c);ins(y,x,c);
}
printf("Case %d: ",++kase);
if(solve())
{
int ans=;
for(int i=;i<=n;i++) ans+=lx[i]+ly[i];
printf("%d\n",-ans);
}
else printf("NO\n");
}
return ;
}
[HDU 3435]
2016-10-27 11:12:02