HDU - 4598 Difference_综合

题意：

有一个图，给图上每个顶点都赋一个实数Ai。如果存在一个正整数T满足下面两个条件，这个图就是一个"difference"。

|Ai| <= T。
(vi, vj) in E <=> |ai - aj| >= T。
如果点i，j构成的边在图中存在，则 |Ai - Aj| >= T；否则 |Ai - Aj| < T。（"<=>" 代表充要条件）

给出图，问这个图是否是一个"difference"。

思路：

有题意可知，任意两个相邻的点，那么他们的值肯定是一正一负，所以随便任意选一个点，假设他是正的，然后染色，如果不能染成功，那就是no，
如果可以染成功，在看看条件2，那是一个充要条件，所以如果a b两个点不相邻，要满足 |a - b| < T.
对于 i j，如果 i j 相邻，且 i 是正数，满足 $a_{i} - a_{j} >= T$ 也就是 $a_{j} - a_{i} <= -T$
对于 i j，如果 i j 不相邻，且 i 是正数，满足 $a_{i} - a_{j} <= T-1$
有可能图不是全联通的，所以要建一个超级原点 0，
如果 i 是正数，满足 $0 <= a_{i} - a_{0} <= T - 1$
如果 i 是负数，满足 $0 <= a_{0} - a_{i} <= T - 1$

知道了所有的式子，对于式子形如 $a - b <= T$ 建立一条从 b 到 a 权值为 T 的边

最好跑一遍spfa，判断是不是又负环，如果有那么就输出来 No，否则就是 Yes。

#include<bits/stdc++.h>
using namespace std;
const int N = 500;
const int INF = 500;
typedef pair<int,int>P;
vector<P>f[N];int n,m;
int s[N][N],dis[N],dep[N];
bool vv[N];bool bfs(int u){queue<int>q;while(!q.empty()) q.pop();q.push(u);dis[u] = 1;while(!q.empty()){u = q.front(); q.pop();for (int i = 1; i <= n; ++i){if (s[u][i] == 1){if (dis[i] == 0) {dis[i] = dis[u] ^ 3;q.push(i);}if (dis[u] == dis[i]) return 1;}}}return 0;
}bool spfa(int u){queue<int>q;q.push(u);dis[u] = 0;vv[u] = 1;while(!q.empty()){u = q.front(); q.pop();vv[u] = 0;for (auto it: f[u]){int v = it.first, w = it.second;if (dis[v] > dis[u] + w){dis[v] = dis[u] + w;if (!vv[v]){q.push(v);dep[v]++;vv[v] = 1;if (dep[v] > 300) return 1;}}}}return 0;
}int main(){int T;scanf("%d",&T);while(T--){scanf("%d",&n);memset(dis, 0, sizeof dis);memset(dep, 0, sizeof dep);for (int i = 1; i <= n; ++i)for (int j = 1; j <= n; ++j)scanf("%1d",&s[i][j]);bool vis = 0;for (int i = 1; i <= n; ++i){if (!dis[i]) vis = vis || bfs(i);if (vis) break;}if (vis){puts("No");continue;} for (int i = 1; i <= n; ++i)for (int j = i + 1; j <= n; ++j){if (s[i][j] == 1){if (dis[i] == 1){f[i].push_back(P{j, -INF});} else {f[j].push_back(P{i, -INF});}} else {if (dis[i] == 1){f[j].push_back(P{i,INF-1});} else {f[i].push_back(P{j,INF-1});}}}for (int i = 1; i<= n; ++i){if (dis[i] == 1){f[0].push_back(P{i, INF-1});f[i].push_back(P{0,0});} else {f[i].push_back(P{0, INF-1});f[0].push_back(P{i, 0});}}vis = 0;for (int i = 0; i <= n; ++i){dis[i] = INF*1000;vv[i] = 0;}if (spfa(0)) puts("No"); else puts("Yes");for (int i = 0; i <= n;++i)f[i].clear();}return 0;
}
/* 3 4 0011 0001 1000 1100 4 0101 1010 0101 10104 0111 1001 1001 1110 3 000 000 000 */