HDU 4598 Difference

Difference

Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 65535/65535 K (Java/Others)
Total Submission(s): 581 Accepted Submission(s): 152

Problem Description

A graph is a difference if every vertex vi can be assigned a real number ai and there exists a positive real number T such that
(a) |a_i| < T for all i and
(b) (v_i, v_j) in E <=> |a_i - a_j| >= T,
where E is the set of the edges.
Now given a graph, please recognize it whether it is a difference.

Input

The first line of input contains one integer TC(1<=TC<=25), the number of test cases.
Then TC test cases follow. For each test case, the first line contains one integer N(1<=N<=300), the number of vertexes in the graph. Then N lines follow, each of the N line contains a string of length N. The j-th character in the i-th line is "1" if (v_i, v_j) in E, and it is "0" otherwise. The i-th character in the i-th line will be always "0". It is guaranteed that the j-th character in the i-th line will be the same as the i-th character in the j-th line.

Output

For each test case, output a string in one line. Output "Yes" if the graph is a difference, and "No" if it is not a difference.

Sample Input

0011

0001

1000

1100

0111

1001

1110

000

Sample Output

Yes

Hint

In sample 1, it can let T=3 and a[sub]1[/sub]=-2, a[sub]2[/sub]=-1, a[sub]3[/sub]=1, a[sub]4[/sub]=2.

Source

2013 ACM-ICPC吉林通化全国邀请赛——题目重现

Recommend

liuyiding

解题：差分约束，完全不懂为什么要这样子。学渣的无奈啊

  1 #include <iostream>
  2 #include <cstdio>
  3 #include <cstring>
  4 #include <cmath>
  5 #include <algorithm>
  6 #include <climits>
  7 #include <vector>
  8 #include <queue>
  9 #include <cstdlib>
 10 #include <string>
 11 #include <set>
 12 #include <stack>
 13 #define LL long long
 14 #define pii pair<int,int>
 15 #define INF 0x3f3f3f3f
 16 using namespace std;
 17 const int maxn = 345,T = 1234;
 18 struct arc{
 19     int u,v,w;
 20     arc(int x = 0,int y = 0,int z = 0){
 21         u = x;
 22         v = y;
 23         w = z;
 24     }
 25 };
 26 vector<int>g[maxn];
 27 vector<int>G[maxn];
 28 vector<arc>e;
 29 char mp[maxn][maxn];
 30 int n,color[maxn],d[maxn],cnt[maxn];
 31 bool in[maxn];
 32 void dfs(int u,int c){
 33     color[u] = c;
 34     for(int i = 0; i < g[u].size(); i++)
 35         if(!color[g[u][i]]) dfs(g[u][i],-c);
 36 }
 37 void add(int u,int v,int w){
 38     e.push_back(arc(u,v,w));
 39     G[u].push_back(e.size()-1);
 40 }
 41 bool spfa(){
 42     queue<int>q;
 43     for(int i = 0; i < n; i++){
 44         d[i] = 0;
 45         cnt[i] = 1;
 46         in[i] = true;
 47         q.push(i);
 48     }
 49     while(!q.empty()){
 50         int u = q.front();
 51         q.pop();
 52         in[u] = false;
 53         for(int i = 0; i < G[u].size(); i++){
 54             arc &temp = e[G[u][i]];
 55             if(d[temp.v] > d[u]+temp.w){
 56                 d[temp.v] = d[u]+temp.w;
 57                 if(!in[temp.v]){
 58                     in[temp.v] = true;
 59                     cnt[temp.v]++;
 60                     if(cnt[temp.v] > n) return true;
 61                     q.push(temp.v);
 62                 }
 63             }
 64         }
 65     }
 66     return false;
 67 }
 68 bool solve(){
 69     for(int i = 0; i < n; i++) if(!color[i]) dfs(i,1);
 70     for(int i = 0; i < n; i++)
 71         for(int j = 0; j < g[i].size(); j++)
 72             if(color[i] == color[g[i][j]]) return false;
 73     for(int i = 0; i < n; i++){
 74         for(int j = i+1; j < n; j++){
 75             if(mp[i][j] == '1')
 76                 color[i] == 1?add(i,j,-T):add(j,i,-T);
 77             else color[i] == 1?add(j,i,T-1):add(i,j,T-1);
 78         }
 79     }
 80     return !spfa();
 81 }
 82 int main() {
 83     int ks,i,j;
 84     scanf("%d",&ks);
 85     while(ks--){
 86         scanf("%d",&n);
 87         for(i = 0; i <= n; i++){
 88             g[i].clear();
 89             G[i].clear();
 90             color[i] = 0;
 91         }
 92         e.clear();
 93         for(i = 0; i < n; i++){
 94             scanf("%s",mp[i]);
 95             for(j = 0; j < n; j++)
 96                 if(mp[i][j] == '1') g[i].push_back(j);
 97         }
 98         solve()?puts("Yes"):puts("No");
 99     }
100     return 0;
101 }

View Code