[HDOJ3435 A new Graph Game]【最佳匹配】

【题目大意】

给出N个点，M条带权无向边。

让你选一些边，使得能用多个圈把图上所有点精确覆盖。输出所有圈的长度之和。

如果不存在这样的圈，输出-1.

【算法分析】

这个是经典题。。。

如果整个图是一个哈密顿回路的话，那么每个点的度都为2。

那么我们把每个点拆开。并给哈密顿圈定义一个方向。

那么一个负责出度，一个负责入度。最佳匹配即可。

【其它】1Y

【CODE】

#include const int N=20005;
const int E=200005;
const int INF=1000000000;
int n,m,e,S,T,cost,Flow;
int v[N],d[N],L[N];
struct edge{int x,y,c,w;edge *next,*op;}g[E],*ls[N],*fa[N];

void addedge(int x,int y,int c,int w){
g[++e].x=x; g[e].y=y; g[e].c=c; g[e].w= w; g[e].next=ls[x]; ls[x]=&g[e]; g[e].op=&g[e+1];
g[++e].x=y; g[e].y=x; g[e].c=0; g[e].w=-w; g[e].next=ls[y]; ls[y]=&g[e]; g[e].op=&g[e-1];
}

void init(){
e=0;
memset(ls,0,sizeof(ls));
int i,x,y,w;
scanf("%d%d",&n,&m);
S=0; T=n+m+1;
for (i=1;i<=m;i++){
scanf("%d%d%d",&x,&y,&w);
addedge(x,y+n,1,w);
addedge(y,x+n,1,w);
}
for (i=1;i<=n;i++){
addedge(n+i,T,1,0);
addedge(S,i,1,0);
}
}

bool spfa(){
int i,head=0,tail=1;
for (i=S;i<=T;i++){
d[i]=INF;
v[i]=0;
}
d[S]=0; v[S]=1; L[1]=S;
while (head!=tail){
head++; if (head>=N) head=0;
for (edge *t=ls[L[head]];t;t=t->next)
if (t->c && d[t->x]+t->wd[t->y]=d[t->x]+t->w;
fa[t->y]=t;
if (!v[t->y]){
v[t->y]=1;
tail++; if (tail>=N) tail=0;
L[tail]=t->y;
}
}
v[L[head]]=0;
}
return d[T]!=INF;
}

void change(){
cost+=d[T];
for (int i=T;i!=S;i=fa[i]->x){
fa[i]->c–;
fa[i]->op->c++;
}
Flow++;
}

void MCMF(){
cost=Flow=0;
while (spfa()) change();
if (Flow!=n) puts("NO");
else printf("%dn",cost,Flow);
}

int main(){
int Tc,i;
scanf("%d",&Tc);
for (i=1;i<=Tc;i++){
printf("Case %d: ",i);
init();
MCMF();       
}
}