SGU_206
不得不说这个题目的思想太奇葩，一时间还是不能很理解……
首先一个贪心的思路就是，石子路的d[i]一定是小于或等于c[i]的，而非石子路的d[j]是一定大于或等于c[j]的，如果我们用x[i]描述石子路谎报的增量那么有x[i]=c[i]-d[i]，用y[j]描述非石子路谎报的增量那么有y[j]=d[j]-c[j]，最后目标自然就是求sum{x[i]}+sum{y[j]}的最小值了。
接着考虑题目中给出的重要条件，即最后要让石子路形成最小生成树，那么对于任意一条非石子路，填加到最小生成树上就会形成一个环，如果这条非石子路d[j]比环上某条石子路的d[i]小的话，那么这条非石子路就可以替换掉那条石子路成为最小生成树上的边，这样就与假设的“石子路形成最小生成树”相矛盾了，因此，对于环上的任意一条石子路都有d[j]>=d[i]。
现在条件都已经分析完了，乍看起来是个很头疼的问题，因为我们要根据推出的这些不等式来确定sum{x[i]}+sum{y[j]}的最小值，这样就可能要用到线性规划这个的东西了，至少现在我还不会线性规划……但如果将原来的不等式加以变形的话，很奇葩地就能KM挂上钩了……
由d[j]>=d[i]，我们可以得到y[j]+c[j]>=c[i]-x[i]，将变量x[i]、x[j]移到一边去就得到了x[i]+y[j]>=c[i]-c[j]，而这个式子和KM中的A[i]+B[j]>=G[i][j]是很像的。再联想到KM求解的过程，实际上就是在满足所有A[i]+B[j]>=G[i][j]的前提条件下，不断缩小A[i]，当缩到不能缩时，也就是当出现A[i]+B[j]==G[i][j]的时候，就会完成一条匹配，于是做完KM之后实际上就保证了sum{A[i]}+sum{B[j]}的值最小了。
这样这个题目的思路就有了，找到所有的d[j]>=d[i]的关系并转化成x[i]+y[j]>=c[i]-c[j]这样的关系，然后连一条i到j的权值为c[i]-c[j]边，如果两边点数不一样的话就补点使两边的点数相等，然后将边补全，补的边的权值都看作0，最后做完KM之后根据A[i]、B[j]的值就可以计算出d[i]、d[j]的值了。在建图的时候，如果c[i]-c[j]<0，可以直接将这条边看成0，因为增量都是正的，所以有一个隐含条件x[i]+y[j]>=0。
#include#include #include #define MAXN 70#define MAXD 410#define MAXM 810#define INF 0x3f3f3f3fint N, M, D, first[MAXN], e, next[MAXM], v[MAXM], w[MAXM], c[MAXM];int g[MAXD][MAXD], visx[MAXD], visy[MAXD], A[MAXD], B[MAXD], slack, yM[MAXD];void add(int x, int y, int z){ v[e] = y, w[e] = z; next[e] = first[x], first[x] = e ++; }int dfs(int cur, int fa, int t, int id, int value){ int i; if(cur == t) return 1; for(i = first[cur]; i != -1; i = next[i]) if(v[i] != fa && dfs(v[i], cur, t, id, value)) { g[i / 2][id] = std::max(g[i / 2][id], w[i] - value); return 1; } return 0;}void init(){ int i, x, y, z; N -= 1; memset(first, -1, sizeof(first)), e = 0; for(i = 0; i < N; i ++) { scanf("%d%d%d", &x, &y, &z); add(x, y, z), add(y, x, z); } memset(g, 0, sizeof(g)); M -= N; for(i = 0; i < M; i ++) { scanf("%d%d%d", &x, &y, &z), c[i] = z; dfs(x, -1, y, i, z); }}int searchpath(int cur, int n){ int i; visx[cur] = 1; for(i = 0; i < n; i ++) if(!visy[i]) { int t = A[cur] + B[i] - g[cur][i]; if(t == 0) { visy[i] = 1; if(yM[i] == -1 || searchpath(yM[i], n)) { yM[i] = cur; return 1; } } else slack = std::min(slack, t); } return 0;}void solve(){ int i, j, n = std::max(N, M); memset(B, 0, sizeof(B[0]) * n); for(i = 0; i < n; i ++) for(j = A[i] = 0; j < n; j ++) A[i] = std::max(A[i], g[i][j]); memset(yM, -1, sizeof(yM[0]) * n); for(i = 0; i < n; i ++) for(;;) { slack = INF; memset(visx, 0, sizeof(visx[0]) * n); memset(visy, 0, sizeof(visy[0]) * n); if(searchpath(i, n)) break; for(j = 0; j < n; j ++) if(visx[j]) A[j] -= slack; for(j = 0; j < n; j ++) if(visy[j]) B[j] += slack; } for(i = 0; i < N; i ++) printf("%d\n", - A[i] + w[i << 1]); for(i = 0; i < M; i ++) printf("%d\n", B[i] + c[i]);}int main(){ while(scanf("%d%d", &N, &M) == 2) { init(); solve(); } return 0; }