hdu1853解题报告

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

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

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

那么在代码中体现出来:

 

// 31MS 272K 
#include<stdio.h>
#include<string.h>

#define MAX 101
#define INF 1<<30-1

int 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 == y
		int 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;
}

个人愚昧观点..欢迎指正与讨论

 

 

更多相关文章
  • http://poj.org/problem?id=1173 发现此题资料甚少,斗胆第一次写一份解题报告[题意]     输入 n(代表二进制位数) k(代表黑条白条总共有几条,条形码是以黑条开始的,再白黑交替出现) m(代表每条最多占多少个二进制位)     输出这种模式的条形码的有多少个?    ...
  • 题目大意:使用两个哈希表来解决哈希冲突的问题.假如现在有两个哈希表分别为:H1,H2 ,大小分别为:n1,n2:现有一数据X需要插入,其插入方法为: 1.计算index1 = X MOD N1,  若哈希表H1的index1位置没有保存数据,则直接将X保存到H1得index1:否则,若哈希表H1的i ...
  • 题目大意:输入一个偶数(x<32),输出这个偶数是由哪两个素数相加所得. 比如:一个偶数26,它可以是3+23,7+19,13+13,这些素数相加所得. 输入输出样例: Sample Input 3 4 26 100 Sample Output 4 has 1 representation(s ...
  • 本题大意: 用天平对一物品进行称重,现有重量不同的砝码,砝码的重量分别为:1,3,9,27,..,3^n.(n<20) 天平的右侧放砝码,左侧放物品或物品和砝码,使得左右两边的重量相等. 现有一个物品,计算左右两边应当分别放多少个多大的砝码才能使得天平平衡. 例如:现在有一个重量为21的物品, ...
  • 好几年没有做ACM了,感觉忘得差不多了,这个做着做着就打瞌睡了!言归正传,下面是我的解题思路: 首先的话,我们可以画一个函数图,以输入数组的下标为X轴,以数组的和为Y轴,当数组和小于零时,我们使用备用的数组和sum2和备用的最小下标min2,并用flag进行标记.具体实现可以参考代码. 需要注意的地 ...
  • 一.原题中文大意. 1      2       3      4       5      6         7     8 9     10       11    12      13     14       15    16 17    18      19    20       21 ...
  • //我是莱鸟,多多交流 //380k //94ms 题目的意思是:每种装备可由多个生产商提供,从每一种装备中选择一个厂家的设备,使得所选的总的各种装备中的最小带宽B与他们的价格之和P的比值B/P达到最大. 解题思路: 准备工作:在输入时,统计所有装备中的最小值min,和每种装备中的最大值max,然后 ...
  • Spring1F Dice(HDU 5012)解题报告及测试数据
    Dice Time Limit:1MS     Memory Limit:65536KB Description There are 2 special dices on the table. On each face of the dice, a distinct number was writt ...
一周排行