首页 > 代码库 > hdu 4598 Difference
hdu 4598 Difference
Difference
Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 65535/65535 K (Java/Others)
Total Submission(s): 621 Accepted Submission(s): 161
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.
(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.
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吉林通化全国邀请赛——题目重现
给你一个图，问是不是满足题目要求的条件，
|a[i]-a[j]| >= T ;对于在图里的边，不在图里的边|a[i]-a[j]| < T
| a[i] | < T ;
我们很容易知道如果 i-j有边，a[i],a[j]符号肯定不同，那么这个就是二分图了，染色法可以做
如果可以染色 我们可以随便取个 T 值。然后构造差分约束方程，
跑最短路判负圈
#include<iostream>#include<cstdio>#include<cstring>#include<algorithm>#include<cmath>#include<queue>#include<vector>#include<set>#include<stack>#include<map>#include<ctime>#include<bitset>#define LL long long#define mod 1000000007#define maxn 410#define pi acos(-1.0)#define eps 1e-8#define INF 0x3f3f3f3fusing namespace std;vector<int>qe[maxn] ;int color[maxn] ,flag,top,val[maxn*maxn] ;int head[maxn],to[maxn*maxn],next1[maxn*maxn];char a[maxn][maxn] ;void Unit(int u,int v,int c){ next1[top] = head[u] ;to[top] = v ; val[top]=c;head[u]=top++;}void dfs(int u,int fa,int c ){ color[u]=c; for(int i = 0 ; i < qe[u].size();i++) { int v = qe[u][i] ; if(v==fa) continue ; if(color[v]==-1) { dfs(v,u,1-c) ; } else if(color[v]==c) { flag=1; return ; } }}int dis[maxn] ,cnt[maxn];bool vi[maxn];bool spfa(int s,int n){ queue<int>q; for(int i = 1 ; i <= n ;i++) { dis[i]=0; vi[i]=1; q.push(i); cnt[i]=0; } int i,u,v; while(!q.empty()) { u = q.front();q.pop(); for( i = head[u] ; i != -1 ; i = next1[i]) { v = to[i] ; if(dis[v] > dis[u]+val[i]) { dis[v]=dis[u]+val[i] ; if(!vi[v]) { vi[v]=true; cnt[v]++; if(cnt[v]>n) return false; q.push(v) ; } } } vi[u]=false; } return true;}int main(){ int j,i,l,g,n; int T,ans1,u,v; cin >> T ; while(T--) { scanf("%d",&n) ; for( i = 1 ; i <= n ;i++){ scanf("%s",a[i]+1) ; qe[i].clear(); } for( i = 1 ; i <= n ;i++) for( j = 1 ; j <= n ;j++)if(a[i][j]==‘1‘){ qe[i].push_back(j); } memset(color,-1,sizeof(color)) ; flag=0; for( i = 1 ; i <= n ;i++)if(color[i]==-1){ dfs(i,-1,1) ; if(flag) break ; } if(flag){ puts("No") ; continue ; } top=0; memset(head,-1,sizeof(head)) ; for( i = 1 ; i <= n ;i++) for( j = i+1 ; j <= n ;j++) { if(a[i][j]==‘1‘) { if(color[i]) Unit(i,j,-maxn) ; else Unit(j,i,-maxn) ; } else { if(color[i]) Unit(j,i,maxn-1); else Unit(i,j,maxn-1) ; } } if(spfa(1,n))puts("Yes") ; else puts("No") ; } return 0 ;}
hdu 4598 Difference
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。