ack ble 最大值 com nod 明显 ems min getch
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=0,w=1;char ch=0;
- while(ch<‘0‘||ch>‘9‘){if(ch==‘-‘)w=-1;ch=getchar();}
- while(ch>=‘0‘&&ch<=‘9‘){x=(x<<1)+(x<<3)+ch-‘0‘;ch=getchar();}
- return x*w;
- }
- const int N=501;
- const int M=10000001;
- struct cow{
- int x;
- int y;
- }e[N],s[3];
- struct node{
- int to;
- int nxt;
- }edge[M];
- struct wzh{
- int u;
- int v;
- }aa[1001],bb[1001];
- int head[N*2],dfn[N*2],low[N*2],to[N*2];
- int t,l,cnt;
- bool instack[N*4];
- 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]=1;
- for(int i=head[u];i!=0;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]=0;
- 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=0;l=0;t=0;
- memset(head,0,sizeof(head));
- memset(dfn,0,sizeof(dfn));
- return;
- }
- int n,ans=-1;
- int a,b;
- void erfen(int l,int r){
- if(l>r)return;
- clr();
- int mid=(l+r)>>1;
- for(int i=1;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=1;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=1;i<=n;i++){
- for(int j=1;j<=n;j++){
- if(i==j)continue;
- int s11=dis(i,1,1,j),s12=dis(i,1,2,j),
- s21=dis(i,2,1,j),s22=dis(i,2,2,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=1;i<=n*2;i++){
- if(!dfn[i])tarjan(i);
- }
- for(int i=1;i<=n;i++){
- if(to[i]==to[i+n]){
- erfen(mid+1,r);
- return;
- }
- }
- ans=mid;
- erfen(l,mid-1);
- return;
- }
- //i表示与s1连,i+n表示与s2连
- int main(){
- n=read();a=read();b=read();
- s[1].x=read();s[1].y=read();s[2].x=read();s[2].y=read();
- for(int i=1;i<=n;i++){
- e[i].x=read();
- e[i].y=read();
- }
- for(int i=1;i<=a;i++){
- aa[i].u=read();
- aa[i].v=read();
- }
- for(int i=1;i<=b;i++){
- bb[i].u=read();
- bb[i].v=read();
- }
- erfen(0,6000000);
- printf("%d\n",ans);
- return 0;
- }
poj2749:Building roads——题解
来源: http://www.bubuko.com/infodetail-2399124.html