bzoj2330 [SCOI2011]糖果题解

?id=2330

题目大意 对这个题我真的不想再多提一句了。 n个人分糖，保证每个人都有糖，有k个限制条件，分别是。

题解 一看就是差分约束了。 差分约束中求最小值用，跑最短路。 权值都是0； ，权值为0； ，，权值为0； 那么不带等号的怎么办呢？ （如果是实数可以不管，就是求得的最值取不到也在误差范围内。） 因为a，b均是整数，所以 ，权值为1； 同理，，权值为1； 然后是与源点0连边。因为每个人都有糖，即，权值为1。

注意事项 本来是一道很裸的差分约束，但是： 某测试点是十万条边连成一条链，如果采用邻接表从表头插入的写法，从源点0连边时如果； 某测试点是时出现了，这种情况应为无解，输出-1，如果不特判，你的spfa将会在毫不知情的情况下陷入死循环（就是邻接表自己连成环了）； dist数组要开longlong。

Code

;const int maxn = 100010, oo = 1000000000, nil = 0;int n, k;int e, pnt[maxn], nxt[maxn << 2], u[maxn << 2], v[maxn<< 2], w[maxn << 2];bool vis[maxn], flag;int times[maxn];long long d[maxn];void addedge(int a, int b, int c){u[++e] = a; v[e] = b; w[e] = c;nxt[e] = pnt[a]; pnt[a] = e;}void init(){int x, a, b;flag = false;scanf(“%d%d”, &n, &k);//跑最长路的时候我喜欢直接把边权加成负的for(int i = n; i > 0; –i){addedge(0, i, -1);}for(int i = 1; i <= k; ++i){scanf(“%d%d%d”, &x, &a, &b);switch(x){case 1: addedge(a, b, 0);addedge(b, a, 0);break;case 2: addedge(a, b, -1);if(a == b){flag = true;}break;case 3: addedge(b, a, 0);break;case 4: addedge(b, a, -1);if(a == b){flag = true;}break;case 5: addedge(a, b, 0);break;default:break;}}}void work(){if(flag){puts(“-1”);return;}memset(d, 0x7f, sizeof(d));memset(vis, 0, sizeof(vis));memset(times, 0, sizeof(times));queue <int> Q;d[0] = 0;vis[0] = true;++times[0];Q.push(0);while(!Q.empty()){int t = Q.front();Q.pop();vis[t] = false;for(int j = pnt[t]; j != nil; j = nxt[j]){if(d[v[j]] > d[t] + w[j]){d[v[j]] = d[t] + w[j];if(!vis[v[j]]){vis[v[j]] = true;++times[v[j]];Q.push(v[j]);(times[v[j]] > n){puts(“-1”);return;}}}}}long long ans = 0;for(int i = 1; i <= n; ++i){ans += d[i];}printf(“%lld\n”, -ans);}int main(){init();work();return 0;}

我不但的回首，伫足，然后时光扔下我轰轰烈烈的向前奔去。