hdu1853答题报告

hdu1853解题报告

题意和解决回路匹配的思路如同hdu3488

(这里我第一次想到最短路，但是对于有回路这个不知道怎么处理，后来看了别人的解题报告才知道KM匹配，但是看到KM之后就自己想...想了很久....还是不知道回路这个地方怎么匹配......其实应该这样来想....总共有N个城市....如果是要形成回路..那么就是环，那么每一个城市都要和指向的城市匹配一次，也要被一个城市指向自己匹配一次...那么匹配的时候我们把所有的N个城市分成两拨，对于每一个城市都匹配一次就得到了一个完全匹配(既每个点都匹配一次，也就是每一个城市匹配一次、被匹配一次).....那么还有一个地方要注意的是：这里有重边...我们应该选择小的边更新)

这里唯一有一点点不同的就是可以存在无回路的情况，那就是有一个点或者多个点没有匹配到.....

那么在代码中体现出来：

// 31MS 272K #include<stdio.h>#include<string.h>#define MAX 101#define INF 1<<30-1int N,M;int map[MAX][MAX];int lx[MAX],ly[MAX],link[MAX],slar[MAX];bool visx[MAX],visy[MAX];bool dfs(int x){visx[x] = true;for(int y = 1; y <= N; y ++){if(visy[y]) continue;// || x == yint t = lx[x] + ly[y] - map[x][y];if(t == 0){visy[y] = true;if(link[y] == -1 || dfs(link[y])){link[y] = x;return true;}}else if(slar[y] > t) slar[y] = t;}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 ++)if(lx[i] < map[i][j])lx[i] = map[i][j];}for(int x = 1; x <=N; x ++){for(i = 1; i <= N ; i ++) slar[i] = INF;while(1){memset(visx,false,sizeof(visx));memset(visy,false,sizeof(visy));if(dfs(x)) break;int d = INF;for(i = 1; i <= N;i ++)if(!visy[i] && d > slar[i]) d = slar[i];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;bool flag = false;for(i = 1; i <= N; i ++)if(link[i] == -1 || map[link[i]][i] == -INF)//这里判断匹配不到的情况{flag=true;break;}if(flag) ans = 1;return -ans;}int main(){int i,j;int a,b,c;while(~scanf("%d%d",&N,&M)){for(i = 1; i <= N; i ++)for(j = 1; j <= N; j ++)map[i][j]=-INF;while(M -- ){scanf("%d%d%d",&a,&b,&c);map[a][b] = map[a][b] > -c ? map[a][b] : -c;//重边选择}printf("%d\n",KM());}return 0;}