loj 1156(二分+最大流）

题目链接：http://acm.hust.edu.cn/vjudge/problem/viewProblem.action?id=26870
思路：由于溢出问题，wa了半天，还以为构图错了呢，查了半天！一看到最大最小问题，就应该想到二分，二分最大距离，然后建图跑最大流验证。
  1 #include<iostream>
  2 #include<cstdio>
  3 #include<cstring>
  4 #include<algorithm>
  5 #include<queue>
  6 using namespace std;
  7 #define MAXN 222
  8 #define MAXM 222222
  9 #define inf 1<<30
 10 #define FILL(a,b) memset(a,b,sizeof(a))
 11 
 12 struct Edge{
 13     int v,cap,next;
 14 }edge[MAXM];
 15 
 16 int n,D,vs,vt,NV,NE;
 17 int head[MAXN];
 18 
 19 void Insert(int u,int v,int cap)
 20 {
 21     edge[NE].v=v;
 22     edge[NE].cap=cap;
 23     edge[NE].next=head[u];
 24     head[u]=NE++;
 25 
 26     edge[NE].v=u;
 27     edge[NE].cap=0;
 28     edge[NE].next=head[v];
 29     head[v]=NE++;
 30 }
 31 
 32 int level[MAXN],gap[MAXN];
 33 void bfs(int vt)
 34 {
 35     FILL(level,-1);
 36     FILL(gap,0);
 37     queue<int>que;
 38     que.push(vt);
 39     level[vt]=0;
 40     gap[0]++;
 41     while(!que.empty()){
 42         int u=que.front();
 43         que.pop();
 44         for(int i=head[u];i!=-1;i=edge[i].next){
 45             int v=edge[i].v;
 46             if(level[v]!=-1)continue;
 47             level[v]=level[u]+1;
 48             gap[level[v]]++;
 49             que.push(v);
 50         }
 51     }
 52 }
 53 
 54 int pre[MAXN],cur[MAXN];
 55 int SAP(int vs,int vt)
 56 {
 57     bfs(vt);
 58     memcpy(cur,head,sizeof(head));
 59     int u=pre[vs]=vs,aug=inf,maxflow=0;
 60     gap[0]=NV;
 61     while(level[vs]<NV){
 62         bool flag=false;
 63         for(int &i=cur[u];i!=-1;i=edge[i].next){
 64             int v=edge[i].v;
 65             if(edge[i].cap>0&&level[u]==level[v]+1){
 66                 flag=true;
 67                 aug=min(aug,edge[i].cap);
 68                 pre[v]=u;
 69                 u=v;
 70                 if(v==vt){
 71                     maxflow+=aug;
 72                     for(u=pre[u];v!=vs;v=u,u=pre[u]){
 73                         edge[cur[u]].cap-=aug;
 74                         edge[cur[u]^1].cap+=aug;
 75                     }
 76                     aug=inf;
 77                 }
 78                 break;
 79             }
 80         }
 81         if(flag)continue;
 82         int minlevel=NV;
 83         for(int i=head[u];i!=-1;i=edge[i].next){
 84             int v=edge[i].v;
 85             if(edge[i].cap>0&&level[v]<minlevel){
 86                 minlevel=level[v];
 87                 cur[u]=i;
 88             }
 89         }
 90         if(--gap[level[u]]==0)break;
 91         level[u]=minlevel+1;
 92         gap[level[u]]++;
 93         u=pre[u];
 94     }
 95     return maxflow;
 96 }
 97 
 98 struct Node{
 99     int d;
100     char flag;
101 }node[MAXN];
102 
103 void Build(int limit)
104 {
105     NE=0;
106     vs=0,vt=2*n+1,NV=vt+1;
107     FILL(head,-1);
108     for(int i=1;i<=n;i++){
109         if(node[i].flag=='B')Insert(i,i+n,2);
110         else if(node[i].flag=='S')Insert(i,i+n,1);
111     }
112     for(int i=1;i<=n;i++){
113         for(int j=i+1;j<=n;j++){
114             if(node[j].d-node[i].d<=limit){
115                 Insert(i+n,j,2);
116             }
117         }
118     }
119     for(int i=1;i<=n;i++){
120         if(node[i].d<=limit)Insert(vs,i,2);
121         if(D-node[i].d<=limit)Insert(i+n,vt,2);
122     }
123     if(D<=limit)Insert(vs,vt,2);
124 }
125 
126 int main()
127 {
128     int _case,t=1;
129     char str[222];
130     scanf("%d",&_case);
131     while(_case--){
132         scanf("%d%d",&n,&D);
133         for(int i=1;i<=n;i++){
134             scanf("%s",str);
135             sscanf(str,"%c-%d",&node[i].flag,&node[i].d);
136         }
137         int low=0,high=D,mid,ans;
138         while(low<=high){
139             mid=(low+high)>>1;
140             Build(mid);
141             if(SAP(vs,vt)>=2){
142                 ans=mid;
143                 high=mid-1;
144             }else
145                 low=mid+1;
146         }
147         printf("Case %d: %d
",t++,ans);
148     }
149     return 0;
150 }
View Code