首页 > ACM题库 > HDU-杭电 > HDU 3526-Computer Assembling[解题报告]HOJ
2014
11-05

HDU 3526-Computer Assembling[解题报告]HOJ

Computer Assembling

问题描述 :

XiaoA is becoming more and more unsatisfied with his computer since he is learning hacker technologies these days but his computer always fails whenever he changes the configurations of the NIC. He buys a new NIC but the motherboard doesn’t recognize it. He then pays for a motherboard from the same company as the NIC. This time the display card is in collision with the motherboard so he cannot even start his computer.
After days of affliction, XiaoA decides to assemble a computer himself. He has to buy n components. Two companies are finally chosen after he searches the web. They both offer all the n components but the prices may vary. There are some pairs of components such that if XiaoA buys them from different companies he has to spend an additional fee to buy adapters to avoid the collision problem.
XiaoA wants to spend as little as possible. Please tell him the minimum dollars he has to pay.

输入:

There are multiple test cases.
For each test case, the first line contains two integers n and m(1<=n<=500, 0<=m<=n*(n-1)/2), indicating the number of components and the number of pairs. The components are conveniently numbered from 1 to n and all pairs are distinct. The next two lines both have n integers(in the range [1, 200]), describing the price in dollar for each component they offer in order. The next m lines contain three integers i, j and c(1<=i, j<=n, i!=j, 1<=c<=200) each, indicating that if he buys component i and j from different companies, he has to spend another c dollars for an adapter.
Proceed to the end of file.

输出:

There are multiple test cases.
For each test case, the first line contains two integers n and m(1<=n<=500, 0<=m<=n*(n-1)/2), indicating the number of components and the number of pairs. The components are conveniently numbered from 1 to n and all pairs are distinct. The next two lines both have n integers(in the range [1, 200]), describing the price in dollar for each component they offer in order. The next m lines contain three integers i, j and c(1<=i, j<=n, i!=j, 1<=c<=200) each, indicating that if he buys component i and j from different companies, he has to spend another c dollars for an adapter.
Proceed to the end of file.

样例输入:

5 3
2 3 4 5 2
1 5 3 6 4
1 2 3
2 3 5
3 4 2

样例输出:

16

#include <iostream>
#include <string.h>
#include <stdio.h>
#define min(a, b) ((a) < (b) ? (a) : (b))
using namespace std;
const int maxn = 505;
const int maxm = maxn * maxn * 2;
const int inf = 0x3f3f3f3f;

int pt[maxm], next[maxm], head[maxn], flow[maxm];
int level[maxn], queue[maxn], pos;
int n, m;

void AddEdge(int a, int b, int c)
{
	pt[++pos] = b;
	next[pos] = head[a];
	head[a] = pos;
	flow[pos] = c;
}

void Connect(int a, int b, int c)
{
	AddEdge(a, b, c);
	AddEdge(b, a, 0);
}

bool bfs(int s, int t)
{
	int qs, qe, v, e;
	memset (level, 0, sizeof level);
	qs = qe = 0;
	queue[qe++] = s;
	level[s] = 1;
	while (qs < qe)
	{
		v = queue[qs++];
		for (e = head[v]; e != -1; e = next[e])
			if (flow[e] > 0 && level[pt[e]] == 0)
			{
				queue[qe++] = pt[e];
				level[pt[e]] = level[v] + 1;
			}
	}
	return level[t] > 0;
}

int Update(int v, int t, int tmpflow)
{
	int e, tmp, res = 0;
	if (v == t) return tmpflow;
	for (e = head[v]; e != -1; e = next[e])
		if (flow[e] > 0 && level[pt[e]] == level[v] + 1)
		{
			tmp = Update(pt[e], t, min(flow[e], tmpflow));
			flow[e] -= tmp; flow[e^1] += tmp;
			res += tmp; tmpflow -= tmp;
			if (tmpflow == 0) break;
		}
	level[v] = -1;
	return res;
}

int dinic(int s, int t)
{
	int res = 0;
	while (bfs(s, t))
		res += Update(s, t, inf);
	return res;
}

void init()
{
	int i, a, b, c;
	pos = -1;
	memset (head, -1, sizeof head);
	for (i = 1; i <= n; i++)
	{
		scanf("%d", &a);
		Connect(0, i, a);
	}
	for (i = 1; i <= n; i++)
	{
		scanf("%d", &a);
		Connect(i, n + 1, a);
	}
	for (i = 0; i < m; i++)
	{
		scanf ("%d%d%d", &a, &b, &c);
		AddEdge(a, b, c);
		AddEdge(b, a, c);
	}
}

void Solve()
{
	int res = dinic(0, n + 1);
	printf("%d\n", res);
}

int main()
{
	while (scanf ("%d%d", &n, &m) != EOF)
	{
		init();
		Solve();
	}
	return 0;
}

  1. “再把所有不和该节点相邻的节点着相同的颜色”,程序中没有进行不和该节点相邻的其他节点是否相邻进行判断。再说求出来的也不一样是颜色数最少的

  2. 第二个方法挺不错。NewHead代表新的头节点,通过递归找到最后一个节点之后,就把这个节点赋给NewHead,然后一直返回返回,中途这个值是没有变化的,一边返回一边把相应的指针方向颠倒,最后结束时返回新的头节点到主函数。