HDU 4598

这道题其实不需要考虑具体数值，但可以肯定的是，相连边的两端点必定有一正一负，至于谁正谁负，并不重要，这是可以思考的，很明显的一个二分图性质，如果不满足此条件，是不可能满足题目第二个条件的。所以首先对题目二分染色。对于T，随意指定一个值即可。

注意题目第二个条件为充要条件，所以要考虑没有相连的两点。

uv相连时，设u是正数,很明显有u-v<=-T

uv不连时,设u是正数,有v-u<=T-1。

对于第一个条件，虚拟一个源点即可。注意对于某点u（正或负）,判断它和零的关系。

我的代码，未A，查不出错，但思路肯定没错。

#include <iostream>

#include <cstdio>

#include <algorithm>

#include <cstring>

#include <queue>

using namespace std;

char mp[305][305];

int col[305];

const int T=400;

struct Edge{

	int u,v,w;

	int next;

}edge[300*300*2];

int head[305],tot;

int dis[305],cnt[305],n; bool vis[305];

bool Dcol(int u){

	for(int j=0;j<n;j++){

		if(mp[u][j]=='1'){

			if(col[j]==0){

				col[j]=col[u]*(-1);

				if(!Dcol(j)){ return false;

				}

			}

			else if(col[j]==col[u]) return false;

		}

	}

	return true;

}

void addedge(int u,int v,int w){

	edge[tot].u=u;

	edge[tot].v=v;

	edge[tot].w=w;

	edge[tot].next=head[u];

	head[u]=tot++;

}

bool spfa(){

	queue<int>q;

	for(int i=0;i<=n;i++){

		dis[i]=1<<30;

	}

	dis[0]=0;

	memset(vis,false,sizeof(vis));

	memset(cnt,0,sizeof(cnt));

	q.push(0);

	vis[0]=true;

	while(!q.empty()){

		int u=q.front(); q.pop();

		vis[u]=false;

		for(int e=head[u];e!=-1;e=edge[e].next){

			int v=edge[e].v;

			if(dis[u]+edge[e].w<dis[v]){

				dis[v]=dis[u]+edge[e].w;

				cnt[v]++;

				if(cnt[v]>n) return false;

				if(!vis[v]){

					q.push(v);

					vis[v]=true;

				}

			}

		}

	}

	return true;

}

int main(){

	int Tc;

	scanf("%d",&Tc);

	while(Tc--){

		scanf("%d",&n);

		memset(col,0,sizeof(col));

		for(int i=0;i<n;i++){

			scanf("%s",mp[i]);

		}

		bool flag=true;

		for(int i=0;i<n;i++){

			if(col[i]==0){

				col[i]=1;

				if(!Dcol(i)){

					flag=false;

					break;

				}

			}

		}

		if(!flag){

			puts("No");

		}

		else{

			memset(head,-1,sizeof(head));

			tot=0;

			int u,v;

			for(int i=0;i<n;i++){

				u=i+1;

				if(col[i]>0){

					addedge(0,u,T-1);

					addedge(u,0,0);

				}

				else{

					addedge(u,0,T-1);

					addedge(0,u,0);

				}

				for(int j=i+1;j<n;j++){

					v=j+1;

					if(col[i]<0) swap(u,v);

					if(mp[i][j]=='1'){

						addedge(u,v,-1*T);

					}

					else{

						if(col[i]==col[j]) continue;

						addedge(v,u,T-1);

					}

				}

			}

			if(spfa()){

				puts("Yes");

			}

			else puts("No");

		}

	}

	return 0;

}

转:

#include<iostream>

#include<cstdio>

#include<cstring>

#include<algorithm>

#include<queue>

#define Maxn 1010

#define Maxm Maxn*Maxn

#define inf 100000000

#define T 400

using namespace std;

int head[Maxn],vi[Maxn],col[Maxn],map[Maxn][Maxn],e,n,cnt[Maxn],dis[Maxn];

void init()

{

    memset(head,-1,sizeof(head));

    memset(vi,0,sizeof(vi));

    memset(map,0,sizeof(map));

    memset(col,-1,sizeof(col));

    e=0;

}

struct Edge{

    int u,next,v,val;

}edge[Maxm];

void addedge(int u, int v)

{

    edge[e].u=u;edge[e].v=v;edge[e].next=head[u];head[u]=e++;

    edge[e].v=u;edge[e].u=v;edge[e].next=head[v];head[v]=e++;

}

void add(int u,int v,int val)

{

    edge[e].u=u,edge[e].v=v,edge[e].val=val,edge[e].next=head[u],head[u]=e++;

}

void find(int u,int c)

{

    int i,j,temp;

    vi[u]=1;

    for(i=head[u];i!=-1;i=edge[i].next){

        temp=edge[i].v;

        if(col[temp]==-1){

            col[temp]=c;

            find(temp,c^1);

        }

    }

}

int spfa()

{

    int i,j,v,u;

    queue<int> q;

    memset(cnt,0,sizeof(cnt));

    memset(vi,0,sizeof(vi));

    for(i=0;i<=n;i++){

        dis[i]=inf;

    }

    dis[0]=0;

    q.push(0);

    while(!q.empty()){

        int u=q.front();

        q.pop();

        vi[u]=0;

        for(i=head[u];i!=-1;i=edge[i].next){

            v=edge[i].v;

            if(dis[v]>dis[u]+edge[i].val){

                dis[v]=dis[u]+edge[i].val;

                cnt[v]++;

                if(cnt[v]>n) return 0;

                if(!vi[v]){

                    q.push(v);

                    vi[v]=1;

                }

            }

        }

    }

    return 1;

}

int solve()

{

    int i,j,u,v;

    for(i=1;i<=n;i++)  if(!vi[i]) find(i,0);

    for(i=0;i<e;i++) if(col[edge[i].u]==col[edge[i].v]) return 0;

    memset(head,-1,sizeof(head));

    e=0;

    for(i=1;i<=n;i++){

        for(j=i+1;j<=n;j++){

            if(!map[i][j]&&col[i]==col[j]) continue;

            u=i,v=j;

            if(col[u]==0)

                swap(u,v);

            if(map[u][v])

                add(u,v,-T);

            else

                add(v,u,T-1);

        }

        if(col[i]==0){

            add(i,0,T-1);

            add(0,i,0);

        }

        else{

            add(0,i,T-1);

            add(i,0,0);

        }

    }

    return spfa();

}

int main()

{

    int t,i,j;

    char str[310];

    scanf("%d",&t);

    while(t--){

        scanf("%d",&n);

        init();

        for(i=1;i<=n;i++){

            scanf("%s",&str);

            for(j=0;j<n;j++){

                if(str[j]=='1'&&!map[i][j+1]){

                    addedge(i,j+1);

                    map[i][j+1]=map[j+1][i]=1;

                }

            }

        }

        if(!solve())

            printf("No\n");

        else

            printf("Yes\n");

    }

    return 0;

}

巴特西

HDU 4598

最新文章

热门文章