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;
}