hdu 4598 Difference(奇圈判定+差分约束)
题意要求(1) |ai| < T for all i (2) (vi, vj) in E <=> |ai - aj| >= T。由于(1)条件的存在,所以(2)条件能成立当且仅当ai和aj一正一负。由此可见,图中某条路上的元素正负值分别为正->负->正->负。。。显然当图中存在奇环的时候是无解的。判断奇环用二分染色,color[i]=0表示假设i节点未被染色,1表示假设i节点权值为正,2为负。如果图中没有奇环呢?对于图中的一条边<u, v>,如果color[u]=1,那么显然a[u]-a[v] >= T,color[u]=2, 也就是 -(a[u]-a[v]) >= T;
而如果<u, v>不是图中的边, 必然有 | a[u]-a[v] | < T。由color数组也同样能得到两个不等式。
得到不等式组后无脑跑spfa判负环就行了。。。光是判负环的spfa是不用考虑加入0节点的,在初始化得时候将每个节点加到队列一次就够了。而且d数组也完全可以初始化为0。因为你只需要判负环而已。
#include<algorithm> #include<iostream> #include<cstring> #include<cstdlib> #include<fstream> #include<sstream> #include<vector> #include<string> #include<cstdio> #include<bitset> #include<stack> #include<queue> #include<cmath> #include<map> #include<set> #define FF(i, a, b) for(int i=a; i<b; i++) #define FD(i, a, b) for(int i=a; i>=b; i--) #define REP(i, n) for(int i=0; i<n; i++) #define CLR(a, b) memset(a, b, sizeof(a)) #define PB push_back #define LL long long #define eps 1e-10 #define debug puts("**debug**") using namespace std; const int maxn = 333; const int T = 1000; struct Edge { int from, to, dist; }; vector<Edge> edges; vector<int> G[maxn]; vector<int> g[maxn]; int n, ncase, color[maxn], flag, d[maxn], cnt[maxn]; bool inq[maxn]; char ch[maxn][maxn]; void init() { REP(i, n) G[i].clear(), g[i].clear(); edges.clear(); CLR(color, 0); } void add(int a, int b, int c) { edges.PB((Edge){a, b, c}); int nc = edges.size(); G[a].PB(nc-1); } void dfs(int u, int c) //二分染色 { color[u] = c; int nc = g[u].size(); REP(i, nc) { int v = g[u][i]; if(!color[v]) dfs(v, 3-c); } } bool spfa() { queue<int> q; REP(i, n) d[i] = cnt[i] = 0, inq[i] = 1, q.push(i); while(!q.empty()) { int u = q.front(); q.pop(); inq[u] = false; REP(i, G[u].size()) { Edge& e = edges[G[u][i]]; if(d[e.to] > d[u] + e.dist) { d[e.to] = d[u] + e.dist; if(!inq[e.to]) { q.push(e.to); inq[e.to] = true; if(++cnt[e.to] > n) return true; } } } } return false; } bool solve() { //判奇圈 REP(i, n) if(!color[i]) dfs(i, 1); REP(i, n) REP(j, g[i].size()) if(color[i] == color[g[i][j]]) return 0; REP(i, n) { FF(j, i+1, n) { if(ch[i][j] == '1') { if(color[i] == 1) add(i, j, -T); else add(j, i, -T); } else { if(color[i] == 1) add(j, i, T-1); else add(i, j, T-1); } } } if(spfa()) return 0; return 1; } int main() { scanf("%d", &ncase); while(ncase--) { init(); scanf("%d", &n); REP(i, n) { scanf("%s", ch[i]); REP(j, n) if(i != j && ch[i][j] == '1') g[i].PB(j); } if(solve()) puts("Yes"); else puts("No"); } return 0; }
补充:软件开发 , C++ ,