2233.cpp

这是哈尔滨工业大学acmOJ的源代码

/*  This Code is Submitted by wywcgs for Problem 2233 on 2006-05-16 at 20:33:58 */ 
#include <cstdio>
#include <vector>
#include <algorithm>
using namespace std;

const int NM = 16;
const int MM = 24;
const int INF = 1 << 28;

class Road {
public:
	int a, b, cost;
	void make() { scanf("%d %d %d", &a, &b, &cost); a--; b--; }
};

int cost, n, m;
bool chose[MM];
Road r[MM];

class Graph {
private:
	int dfn[NM], cnt, low[NM];
	bool dfs(int, int);
public:
	vector<int> nei[NM];
	void clear();
	void insert(const Road&);
	bool biconnect();
};
bool Graph::dfs(int p, int prev) {
	dfn[p] = cnt++; low[p] = INF; int i;
	for(i = 0; i < nei[p].size(); i++) {
		int o = nei[p][i];
		if(o == prev) continue;
		if(dfn[o] == -1 && !dfs(o, p)) return false;
		low[p] = min(low[p], dfn[o]);
		if(dfn[o] > dfn[p] && low[o] > dfn[p]) return false;
		low[p] = min(low[p], low[o]);
	}
	return true;
}
void Graph::clear() {
	int i;
	for(i = 0; i < n; i++) nei[i].clear();
}
void Graph::insert(const Road& ro) {
	nei[ro.a].push_back(ro.b); nei[ro.b].push_back(ro.a);
}
bool Graph::biconnect() {
	memset(dfn, -1, sizeof(dfn)); cnt = 0; 
	if(!dfs(0, -1)) return false;
	int i;
	for(i = 0; i < n; i++)
		if(dfn[i] == -1) return false;
	return true;
}

Graph g;

void enumer(int, int, int);

int main()
{
	int t, i;

	for(t = 1; scanf("%d %d", &n, &m) != EOF && n != 0; t++) {
		for(i = 0; i < m; i++) r[i].make();
		cost = INF; enumer(0, 0, 0);
		if(cost == INF) printf("There is no reliable net possible for test case %d.\n", t);
		else printf("The minimal cost for test case %d is %d.\n", t, cost);
	}
	
	return 0;
}

void enumer(int b, int cn, int cc)
{
	if(cc >= cost) return;
	else if(m-b+cn < n) return;
	else if(b != m) {
		chose[b] = false; enumer(b+1, cn, cc);
		chose[b] = true; enumer(b+1, cn+1, cc+r[b].cost);
	} else {
		int i; g.clear();
		for(i = 0; i < m; i++)
			if(chose[i]) g.insert(r[i]);
		if(g.biconnect()) cost = min(cost, cc);
	}
}