hdu3488解题报告

发布时间:2016-12-6 22:12:45 编辑:www.fx114.net 分享查询网我要评论
本篇文章主要介绍了"hdu3488解题报告",主要涉及到hdu3488解题报告方面的内容,对于hdu3488解题报告感兴趣的同学可以参考一下。

题意:一个王国里有很多个城市,这些城市之间有很多单向的路连接起来,并且存在一个或者多个回路,那么这里求出走几个回路之后访问所有的城市的最小路径距离, 分析:这里我第一次想到最短路,但是对于有回路这个不知道怎么处理,后来看了别人的解题报告才知道KM匹配,但是看到KM之后就自己想...想了很久....还是不知道回路这个地方怎么匹配......其实应该这样来想....总共有N个城市....如果是要形成回路..那么就是环,那么每一个城市都要和指向的城市匹配一次,也要被一个城市指向自己匹配一次...那么匹配的时候我们把所有的N个城市分成两拨,对于每一个城市都匹配一次就得到了一个完全匹配(既每个点都匹配一次,也就是每一个城市匹配一次、被匹配一次).....那么还有一个地方要注意的是:这里有重边...我们应该选择小的边更新 那么上马: // 78MS 396K #include<stdio.h> #include<string.h> #define MAX 7 #define INF 1<<30-1 int w[MAX][MAX]; int link[MAX],lx[MAX],ly[MAX],slar[MAX]; bool visx[MAX],visy[MAX]; int N,M; bool dfs(int u) { visx[u] = true ; for(int v = 1; v <= N ; v ++) { if(visy[v]) continue; // int t = lx[u] + ly[v] -w[u][v]; if(t == 0) { visy[v] = true; if(link[v] == -1 || dfs(link[v])) { link[v] = u; return true; } } else slar[v] =slar[v] > t ? t:slar[v]; } return false; } int KM() { int i,j; memset(ly,0,sizeof(ly)); memset(link,-1,sizeof(link)); for(i = 1; i <= N; i ++) { lx[i] = -INF; for(j = 1; j <= N; j ++) lx[i] = lx[i] > w[i][j] ? lx[i] : w[i][j]; } for(int u = 1; u <= N ; u ++) { for(i = 1; i <= N; i ++) slar[i] = INF; while(1) { memset(visx,false, sizeof(visx)); memset(visy,false,sizeof(visy)); if(dfs(u)) break; int d=INF; for(i = 1 ;i <= N; i ++) if(!visy[i]) d = d > slar[i] ? slar[i] : d; for(i =1 ; i <= N; i ++) if(visx[i]) lx[i] -= d; for(i =1 ;i <= N; i ++) if(visy[i]) ly[i] += d; else slar[i] -= d; } } int ans=0; for(i = 1; i <= N; i ++) ans+=w[link[i]][i]; return ans; } int main() { int i,j; int T; scanf("%d",&T); while(T--) { int a,b,c; scanf("%d%d",&N,&M); for(i = 1 ; i <= N ; i ++) for(j = 1; j <= N ;j ++) w[i][j] = -INF; for(i = 0; i < M; i ++) { scanf("%d%d%d",&a,&b,&c); w[a][b]=w[a][b] > -c ? w[a][b] : -c; //重边选择 } printf("%d\n",-KM()); } return 0; }

上一篇:SilkTest Q&A 8
下一篇:handler详解

相关文章

相关评论