首页 > 代码库 > HDU 4966 GGS-DDU
HDU 4966 GGS-DDU
题意:
你有n个课程 每个课程有一个规定的毕业学分 修学分有m种方式 每种方式要求先修到x课程x‘学分以上才能花费money去修y课程并且将学分修到y‘ 问 最少花费多少可以毕业
思路:
一开始想费用流 建完图发现一个问题解决不掉 那就是 一条边如果流过多次怎样才能让费用只计算一次 所以换思路
我们知道 为了应付“ 学分修到y‘ ”这个条件 高层学分一定要“覆盖”低层学分 那么就想到以每个学分为一个点 高层向低层连边 费用为0 同时修学分的方式是输入的 直接建边 费用为输入费用 一开始只能走到0学分 所以超级源点向所有0学分连边 费用0 那么此时我们想要的是从源点花最小费用走到所有点 这就是有向图最小生成树 即最小树形图
代码:
#include<cstdio> #include<cstring> #include<algorithm> #include<queue> using namespace std; #define M 610 #define inf 2000000000 int n, m, ans, tot, S; int head[M], id[M], in[M], pre[M], vis[M], node[M][M], s[M]; struct ed { int u, v, w, next; } ed[M * M]; int ZL(int root, int V, int E) { int ret = 0; for (;;) { for (int i = 0; i < V; i++) { id[i] = -1; vis[i] = -1; in[i] = inf; } for (int i = 0; i < E; i++) { int u = ed[i].u; int v = ed[i].v; if (ed[i].w < in[v] && u != v) { pre[v] = u; in[v] = ed[i].w; } } for (int i = 0; i < V; i++) { if (i == root) continue; if (in[i] == inf) return -1; } int cnt = 0; in[root] = 0; for (int i = 0; i < V; 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] = cnt; id[v] = cnt++; } } if (cnt == 0) break; for (int i = 0; i < V; i++) if (id[i] == -1) id[i] = cnt++; for (int i = 0; i < E; i++) { int u = ed[i].u; int v = ed[i].v; ed[i].u = id[u]; ed[i].v = id[v]; if (id[u] != id[v]) ed[i].w -= in[v]; } V = cnt; root = id[root]; } return ret; } void add(int U, int V, int W) { ed[tot].u = U; ed[tot].v = V; ed[tot].w = W; ed[tot].next = head[U]; head[U] = tot++; } int main() { int i, j, k, u, v, tmp; while (scanf("%d%d", &n, &m) != EOF) { if (!n && !m) break; k = 0; for (i = 1; i <= n; i++) { scanf("%d", &s[i]); for (j = 0; j <= s[i]; j++) node[i][j] = k++; } S = k++; tot = 0; memset(head, -1, sizeof(head)); for (i = 1; i <= n; i++) { add(S, node[i][0], 0); for (j = 1; j <= s[i]; j++) add(node[i][j], node[i][j - 1], 0); } for (i = 1; i <= m; i++) { scanf("%d%d", &u, &v); tmp = node[u][v]; scanf("%d%d", &u, &v); v = node[u][v]; u = tmp; scanf("%d", &tmp); add(u, v, tmp); } ans = ZL(S, k, tot); printf("%d\n", ans); } return 0; }
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。