首页 > ACM题库 > HDU-杭电 > HDU 3212-Card Collection[解题报告]HOJ
2014
03-06

HDU 3212-Card Collection[解题报告]HOJ

Card Collection

问题描述 :

In Card Captor Sakura, Sakura is a lovely girl. One day, she opens a magic box containing many cards. Every card has a respective natural force in the real world, such as wind, water, YY, LMY, and so on. Suddenly a gust of wind blows away these cards. Sakura only has a card called “THE_WINDY” in her hand. Sakura knows if any card is not found, disaster comes. So she must collect all the cards. Cards can only be collected one by one. Suppose there are N cards to be collected. It takes Ti to collect the ith card, 1≤i≤N. For the ith card, there is a corresponding card Pi. If card Pi has been collected, it only takes time ti to collect the ith card, where ti<Ti.

Your task is to help Sakura design a schedule that takes the shortest time to collect all cards.

输入:

The input consists of several test cases. Each test case starts with a line giving the number N of cards (1≤N≤100). Each of the next N lines describes a card.

Every card has the format: Name1 Ti Name2 ti, where Name1 and Name2 are cards’ names, consisting of uppercase letters and underlines. The length of cards’ names is no more than 20 characters. Card Name1 is a card to be collected. It takes Ti to collect Card Name1 without Card Name2. And it takes ti to collect Card Name1 with Card Name2, where ti<Ti.

End of input is indicated by a line consisting of a single 0.

输出:

The input consists of several test cases. Each test case starts with a line giving the number N of cards (1≤N≤100). Each of the next N lines describes a card.

Every card has the format: Name1 Ti Name2 ti, where Name1 and Name2 are cards’ names, consisting of uppercase letters and underlines. The length of cards’ names is no more than 20 characters. Card Name1 is a card to be collected. It takes Ti to collect Card Name1 without Card Name2. And it takes ti to collect Card Name1 with Card Name2, where ti<Ti.

End of input is indicated by a line consisting of a single 0.

样例输入:

5
THE_FLY 67 THE_WINDY 39
THE_SHADOW 97 THE_WINDY 49
THE_WATER 139 THE_FLY 69
THE_RAIN 37 THE_WATER 18
THE_WOOD 5 THE_RAIN 1
1
THE_LOOP 35 THE_LOOP 25
0

样例输出:

176
35

#include <iostream>
#include <cstring>
#include <cstdio>
#include <string>
#include <map>
using namespace std;
#define maxn 105
#define type int
const int inf = ~0u >> 1;
struct edge
{
	int u,v;
	type cost;
	edge(){}
	edge(int _u,int _v,type _c):u(_u),v(_v),cost(_c){}
}e[maxn * maxn];
int pre[maxn],id[maxn],vis[maxn];
type in[maxn];
type dirmst(int root,int nv,int ne)
{
	type ret = 0;
	while(1)
	{
		fill(in,in + nv,inf);
		for(int i = 0;i < ne;i++)
		{
			int u = e[i].u;
			int v = e[i].v;
			if(e[i].cost < in[v] && u != v)
			{
				pre[v] = u;
				in[v] = e[i].cost;
			}
		}
		for(int i = 0;i < nv;i++)
		{
			if(i == root)
				continue;
			if(in[i] == inf)
				return -1;
		}
		int cntnode = 0;
		fill(id,id + nv,-1);
		fill(vis,vis + nv,-1);
		in[root] = 0;
		for(int i = 0;i < nv;i++)
		{
			ret += in[i];
			int v = i;
			while(vis[v] != i && id[v] == -1 && v != root)
			{
				vis[v] = i;
				v = pre[v];
			}
			if(v != root && id[v] == -1)
			{
				for(int u = pre[v]; u != v;u = pre[u])
					id[u] = cntnode;
				id[v] = cntnode++;
			}
		}
		if(cntnode == 0)
			break;
		for(int i = 0;i < nv;i++)
			if(id[i] == -1)
				id[i] = cntnode++;
		for(int i = 0;i < ne;i++)
		{
			int v = e[i].v;
			e[i].u = id[e[i].u];
			e[i].v = id[e[i].v];
			if(e[i].u != e[i].v)
				e[i].cost -= in[v];
		}
		nv = cntnode;
		root = id[root];
	}
	return ret;
}
int main()
{
	int n;
	while(scanf("%d",&n) == 1 && n)
	{
		map <string,int> M;
		M["THE_WINDY"] = 2;
		int cnt = 3;
		string a,b;
		int w1,w2;
		int m = 0;
		int tot = 0;
		for(int i = 0;i < n;i++)
		{
			cin >> a >> w1 >> b >> w2;
			if(M[a] == 0)
				M[a] = cnt++;
			if(M[b] == 0)
				M[b] = cnt++;
			e[m++] = edge(1,M[a],w1);
			tot += w1;
			if(M[a] != M[b])
			{
				e[m++] = edge(M[b],M[a],w2);
				tot += w2;
			}
		}
		e[m++] = edge(0,1,tot + 1);
		e[m++] = edge(0,2,tot + 1);
		int ans = dirmst(0,cnt,m);
		printf("%d\n",ans - (tot + 1) * 2);
	}
}

  1. 如果两个序列的最后字符不匹配(即X [M-1]!= Y [N-1])
    L(X [0 .. M-1],Y [0 .. N-1])= MAX(L(X [0 .. M-2],Y [0 .. N-1]),L(X [0 .. M-1],Y [0 .. N-1])
    这里写错了吧。

  2. Gucci New Fall Arrivals

    This is really nice to know. I hope it will be successful in the future. Good job on this and keep up the good work.

  3. 其实国内大部分公司对算法都不够重视。特别是中小型公司老板根本都不懂技术,也不懂什么是算法,从而也不要求程序员懂什么算法,做程序从来不考虑性能问题,只要页面能显示出来就是好程序,这是国内的现状,很无奈。