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) |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吉林通化全国邀请赛——题目重现

给你一个图，问是不是满足题目要求的条件，

|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 0x3f3f3f3f
using 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 ;
}

View Code