poj1275

建图规则：

注意，当约束条件是>=的时候，采用最长路。如果不想敲最长路（其实就在spfa里面改一个地方。。）的话，可以把他们都同时乘以-1即可了。

例如s[i-1]-s[i]>=-t[i] ==> s[i]-s[i-1]<=t[i] ==> add_edge(i,i-1,t[i])。

#include <iostream>
#include <queue>

using namespace std;

#define MAXN 25
#define inf 1 << 20

struct node {
	int to, w, next;
} edge[MAXN * 30];

int adj[MAXN], dis[MAXN], c[MAXN]; //adj->head, dis->distance, c->count of visited;
bool vis[MAXN]; //vis->visted
int cnt; //cnt->count of node(s)

int r[MAXN], t[MAXN];

void add_edge(int u, int v, int w) {
	edge[cnt].to = v;
	edge[cnt].w = w;
	edge[cnt].next = adj[u];
	adj[u] = cnt++;
}

void init() {
	cnt = 0;
	for (int i = 0; i < MAXN; i++) {
		adj[i] = -1, dis[i] = inf, vis[i] = false, c[i] = 0;
	}
	dis[0] = 0;
}

void build(int ans) {
	init();
	add_edge(0, 24, -ans);
	for (int i = 1; i < MAXN; i++) {
		add_edge(i - 1, i, 0);
		add_edge(i, i - 1, t[i]);
	}
	for (int j = 1; j < MAXN; j++) {
		int i = (j + 8) % 24;
		if (i > j) {
			add_edge(j, i, -r[i]);
		}
		else if (i < j) {
			add_edge(j, i, -r[i] + ans);
		}
	}
}

bool spfa(int ans) {
	queue <int> q;
	q.push(0);
	vis[0] = true;
	c[0] = 1;
	while (!q.empty()) {
		int p, t = q.front();
		q.pop();
		p = adj[t];
		vis[t] = false;
		while (p != -1) {
			if (dis[edge[p].to] > dis[t] + edge[p].w) {
				dis[edge[p].to] = dis[t] + edge[p].w;
				if (!vis[edge[p].to]) {
					vis[edge[p].to] = true;
					q.push(edge[p].to);
					c[edge[p].to]++;
					if (c[edge[p].to] > 24) {
						return false;
					}
				}
			}
			p = edge[p].next;
		}
	}
	if (dis[24] == -ans) return true;
	else return false;
}

int main() {
	int T;
	cin >> T;
	while (T--) {
		for (int i = 1; i <= 24; i++) {
			cin >> r[i];
			t[i] = 0;
		}
		int n;
		cin >> n;
		for (int i = 0; i < n; i++) {
			int temp;
			cin >> temp;
			t[temp + 1]++;
		}
		bool flag = true;
		for (int i = 0; i <= n; i++) { //0->super source
			build(i);
			if (spfa(i)) {
				cout << i << endl;
				flag = false;
				break;
			}
		}
		if (flag) {
			cout << "No Solution" << endl;
		}
	}
}

poj1275,布布扣,bubuko.com

poj1275

原文：http://blog.csdn.net/zhengnanlee/article/details/19966345