如果本网站登录不畅，可以从以下地址访问：http://code.hdu.edu.cn
Difference
Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 65535/65535 K (Java/Others) Total Submission(s): 236 Accepted Submission(s): 67
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
3 4 0011 0001 1000 1100 4 0111 1001 1001 1110 3 000000 000
Sample Output
Hint
Source
2013 ACM-ICPC吉林通化全国邀请赛——题目重现
Recommend
liuyidin
上学期的通化现场赛没A的差分约束，今天终于知道咋解了，其实也不难嘛！
思路：先判二分图，标记，然后任意选某种标记为正节点，我选颜色0，有边的需要满足 正节点-负节点>=T 无边的满足正节点-负节点<T 对于|V|<T建个虚节点
此节点权为0,0<=正节点 -0<T 0<=0-负节点<T
建图，轻松搞定。
#include<cstdio>#include<cstring>#include<iostream>#include<queue>#define FOR(i,a,b) for(int i=a;i<=b;++i)#define clr(f,z) memset(f,z,sizeof(f))using namespace std;const int mm=330;const int T=330;bool vis[mm][mm],has[mm];int id[mm];int g[mm][mm];int dis[mm];int col[mm];int n;bool get(){ char z; while(1) { z=getchar(); if(z=='1')return 1; if(z=='0')return 0; }}void paint(int u,bool cor){ if(col[u]!=-1)return; col[u]=cor; FOR(i,1,n) if(vis[u][i]) paint(i,cor^1);}bool spfa(int u){ int v; clr(dis,0x3f);clr(has,0);clr(id,0); dis[u]=0;has[u]=1;id[u]++; queue<int>Q;Q.push(u); while(!Q.empty()) { u=Q.front();Q.pop();has[u]=0; for(int i=0;i<=n;++i) { if(dis[i]>dis[u]+g[u][i]) { dis[i]=dis[u]+g[u][i]; if(!has[i]) { has[i]=1;Q.push(i);id[i]++; if(id[i]>n)return 0; } } } } return 1;}bool judge(){ clr(col,-1); FOR(i,1,n)paint(i,0); FOR(i,1,n)FOR(j,1,n) if(vis[i][j]&&col[i]==col[j])return 0; clr(g,0x3f); FOR(i,1,n)FOR(j,1,n)//0为正点 有边的 u->v>=T { if(vis[i][j]) { if(col[i])g[i][j]=-T;///i-j<=-T else g[j][i]=-T;///j-i<=-T; } else { if(col[i])g[j][i]=T-1;///j-i<T else g[i][j]=T-1;///i-j<T } } ///0 虚节点 FOR(i,1,n) { if(col[i])g[0][i]=T-1,g[i][0]=0;///0-i<T i-0>=0 else g[i][0]=T-1,g[0][i]=0; } return spfa(0);}int main(){ int cas; while(~scanf("%d",&cas)) { while(cas--) { scanf("%d",&n); FOR(i,1,n)FOR(j,1,n) vis[i][j]=get(); if(judge()) printf("Yes\n"); else printf("No\n"); } }}