首页 > 代码库 > HDU 4598 Difference

HDU 4598 Difference

2024-07-18 18:09:46   219人阅读

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) |ai| < T for all i and 
(b) (vi, vj) in E <=> |ai - aj| >= 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 (vi, vj) 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
3
4
0011
0001
1000
1100
4
0111
1001
1001
1110
3
000
000
000
 

 

Sample Output
Yes
No
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

 

 
 
 


联系
我们