POJ2749：Building roads—

http://poj.org/problem?id=2749

（这个约翰的奶牛真多事…………………………）

i表示u与s1连，i+n表示u与s2连。

老规矩，u到v表示取u必须取v。

那么对于互相打架的奶牛u，v，有：

add(u,v+n);add(v,u+n);

add(u+n,v);add(v+n,u);

对于互为朋友的奶牛u，v，有：

add(u,v);add(v,u);

add(u+n,v+n);add(v+n,u+n);

但这远远不够，我们需要求最大值最小……

二分？但是我们怎么边处理矛盾边的距离？

那么我们也想把连边处理成冲突。

对于奶牛i，j，sxy表示i到x到y到j的距离，mid是我们二分的最大值最小。

那么显然，对于s>mid，那么一定是矛盾的，此时明显我们要采取相反的方法。

因为我们i和j的循环方式都是1-n，所以我们使i不变，把j变一下即可。

用代码表示就是：

if(s11>mid)add(i,j+n);

if(s12>mid)add(i,j);

if(s21>mid)add(i+n,j+n);

if(s22>mid)add(i+n,j);

（然而我还是查了题解的……我真菜）

#include<stack>

#include<cstdio>

#include<cstring>

#include<vector>

#include<iostream>

#include<algorithm>

using namespace std;

typedef long long ll;

inline int read(){

    int x=,w=;char ch=;

    while(ch<''||ch>''){if(ch=='-')w=-;ch=getchar();}

    while(ch>=''&&ch<=''){x=(x<<)+(x<<)+ch-'';ch=getchar();}

    return x*w;

}

const int N=;

const int M=;

struct cow{

    int x;

    int y;

}e[N],s[];

struct node{

    int to;

    int nxt;

}edge[M];

struct wzh{

    int u;

    int v;

}aa[],bb[];

int head[N*],dfn[N*],low[N*],to[N*];

int t,l,cnt;

bool instack[N*];

stack<int>q;

inline void add(int u,int v){

    cnt++;

    edge[cnt].to=v;

    edge[cnt].nxt=head[u];

    head[u]=cnt;

    return;

}

void tarjan(int u){

    t++;

    dfn[u]=t;

    low[u]=t;

    q.push(u);

    instack[u]=;

    for(int i=head[u];i!=;i=edge[i].nxt){

    int v=edge[i].to;

    if(!dfn[v]){

        tarjan(v);

        low[u]=min(low[u],low[v]);

    }else if(instack[v]){

        low[u]=min(low[u],dfn[v]);

    }

    }

    if(low[u]==dfn[u]){

    int v;

    l++;

    do{

        v=q.top();

        q.pop();

        instack[v]=;

        to[v]=l;

    }while(v!=u);

    }

    return;

}

inline int dis(int a,int k1,int k2,int b){

    return

    abs(s[k1].x-e[a].x)+abs(s[k1].y-e[a].y)+

    abs(s[k1].x-s[k2].x)+abs(s[k1].y-s[k2].y)+

    abs(s[k2].x-e[b].x)+abs(s[k2].y-e[b].y);

}

inline void clr(){

    cnt=;l=;t=;

    memset(head,,sizeof(head));

    memset(dfn,,sizeof(dfn));

    return;

}

int n,ans=-;

int a,b;

void erfen(int l,int r){

    if(l>r)return;

    clr();

    int mid=(l+r)>>;

    for(int i=;i<=a;i++){

    int u=aa[i].u;int v=aa[i].v;

    add(u,v+n);add(v,u+n);

    add(u+n,v);add(v+n,u);

    }

    for(int i=;i<=b;i++){

    int u=bb[i].u;int v=bb[i].v;

    add(u,v);add(v,u);

    add(u+n,v+n);add(v+n,u+n);

    }

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

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

        if(i==j)continue;

        int s11=dis(i,,,j),s12=dis(i,,,j),

        s21=dis(i,,,j),s22=dis(i,,,j);

        if(s11>mid)add(i,j+n);

        if(s12>mid)add(i,j);

        if(s21>mid)add(i+n,j+n);

        if(s22>mid)add(i+n,j);

    }

    }

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

    if(!dfn[i])tarjan(i);

    }

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

    if(to[i]==to[i+n]){

        erfen(mid+,r);

        return;

    }

    }

    ans=mid;

    erfen(l,mid-);

    return;

}

//i表示与s1连，i+n表示与s2连

int main(){

    n=read();a=read();b=read();

    s[].x=read();s[].y=read();s[].x=read();s[].y=read();

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

    e[i].x=read();

    e[i].y=read();

    }

    for(int i=;i<=a;i++){

    aa[i].u=read();

    aa[i].v=read();

    }

    for(int i=;i<=b;i++){

    bb[i].u=read();

    bb[i].v=read();

    }

    erfen(,);

    printf("%d\n",ans);

    return ;

}

巴特西

POJ2749：Building roads——题解

最新文章

热门文章