HDU 4996 GGS

HDU 4996 GGS"/>

HDU 4996 GGS

思路;

首先,我们可以想到可以把每门课程的每个等级都看成一个点,然后我们可以知道对于同一门课程,高等级向低等级走花费为0.

因此我们可以直接用每个课程每个等级建图,然后将每门课程的高等级向低等级连一条权值为0的边.对于辅导班,我们可以直接连接对应的课程和等级...那么对于虚根呢..其实我们很容易想到.虚根应该与每门课程等级为0的点相连.权值直接设计为0即可

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int N = 1e3 + 5;
const int M = 2e4;
const long long Inf = 1e12;
long long d[N];
int ID[N], vis[N], pre[N], pos;
struct edge {int u, v;long long cost;
} es[M];
long long MST(int root, int V, int E) {long long res = 0;while(true) {for(int i = 1; i < V; i += 1)d[i] = Inf;for(int i = 0; i < E; i += 1) {int u = es[i].u;int v = es[i].v;if(d[v] > es[i].cost && u != v) {d[v] = es[i].cost;pre[v] = u;//if(u == root) pos = i;}}for(int i = 1; i < V; i += 1) {if(i == root)continue;if(d[i] == Inf)return -1;}int c;d[root] = c = 0;memset(vis, -1, sizeof(vis));memset(ID, -1, sizeof(ID));for(int i = 1; i < V; i += 1) {int v = i;res += d[i];while(ID[v] == -1 && vis[v] != i && v != root) {vis[v] = i;v = pre[v];}if(ID[v] == -1 && v != root) {c += 1;for(int u = pre[v]; u != v; u = pre[u])ID[u] = c;ID[v] = c;}}if(!c)break;for(int i = 1; i < V; i += 1) {if(ID[i] == -1) {c += 1;ID[i] = c;}}for(int i = 0; i < E; i += 1) {int u = es[i].u;int v = es[i].v;es[i].u = ID[u];es[i].v = ID[v];if(ID[u] != ID[v])es[i].cost -= d[v];}V = c;root = ID[root];}return res;
}
int prefix[N];
int main() {int n, M, x, y;while(~scanf("%d%d", &n, &M)) {if(n + M == 0)break;for(int i = 1; i <= n; i += 1) {scanf("%d", &x);prefix[i] = prefix[i - 1] + x + 1;}int V = prefix[n] + 1;int E = 0;for(int i = 1; i <= n; i += 1) {es[E] = edge{V, prefix[i - 1] + 1, 0};E += 1;for(int k = prefix[i]; k > prefix[i - 1] + 1; --k) {es[E] = edge{k, k - 1, 0};E += 1;}}while(M--) {int c, l1, d, l2;long long money;scanf("%d%d%d%d%lld", &c, &l1, &d, &l2, &money);es[E] = edge{prefix[c - 1] + l1 + 1, prefix[d - 1] + l2 + 1, money};E += 1;}long long res = MST(V, V + 1, E);if(res == -1)printf("-1\n");elseprintf("%lld\n", res);}return 0;
}