Online JudgeProblem SetAuthorsOnline ContestsUser
Web Board
F.A.Qs
Statistical Charts
Problems
Submit Problem
Online Status
Prob.ID:
Register
Authors ranklist
Current Contest
Past Contests
Scheduled Contests
Award Contest
Register

## dinic + 二分差值 + 枚举上下界

Posted by zspzspzsp at 2014-11-13 12:55:16 on Problem 3189
```#include<stdio.h>
#include<queue>
#include<string.h>
#define INF 100000000
#define N 2005
using namespace std;
int tot;
struct map
{
int date;
int next;
int value;
}cun[2000000];
struct cow
{
int like[30];
}cc[1005];
struct dian
{
int x;
int t;
} old,xin;

int deep[N],n,b;
int list[N],value[N];
int listt[N];
{
cun[++tot].date=b;
cun[tot].value=c;
cun[tot].next=list[a];
list[a]=tot;

cun[++tot].date=a;
cun[tot].value=0;
cun[tot].next=list[b];
list[b]=tot;
}
int BFS(int s,int t,int n)
{

xin.x=s;
xin.t=0;
//printf("!\n");
queue<dian>Q;
Q.push(xin);
memset(deep,255 ,sizeof(deep));
deep[s]=0;
while(!Q.empty())
{
old=Q.front();
Q.pop();
for(int k=list[old.x];k;k=cun[k].next)
{

int c=cun[k].value;
xin.x=cun[k].date;
//       printf("%d\n",xin.x);
xin.t=old.t+1;
//       printf("%d\n",deep[xin.x]);
if(deep[xin.x]!=-1||c==0) { continue;}
deep[xin.x]=xin.t;

Q.push(xin);

}

}
for(int i=0;i<=n;i++)
listt[i]=list[i];
return deep[t]!=-1 ;
}
int mmin(int a,int b)
{
if(a<b)  return a;
else return b;
}
int DFS(int s,int t,int min)
{
if(s==t)   return   min;
int neww=0;
for(int k=listt[s];k;k=cun[k].next)
{
listt[s]=k;
int c=cun[k].value;
int date=cun[k].date;
if(c==0||deep[date]!=deep[s]+1) continue;
int m=DFS(date,t,mmin(c,min-neww));
neww+=m;
cun[k].value-=m;
cun[k^1].value+=m;
if(neww==min)  break;

}
if(neww==0)    deep[s]=0;
return neww;
}
int dinic(int s,int t,int n)
{
int num=0;
//    printf("%d\n",BFS(s,t,n));
while(BFS(s,t,n))
{
// printf("!\n");
num+=DFS(s,t,INF);
}
return num;
}
int init(int x,int y)
{
memset(list,0,sizeof(list));
tot=1;
int s=n+b+10,t=s+1;
for(int i=1;i<=n;i++)
for(int i=n+1;i<=n+b;i++)
for(int i=1;i<=n;i++)
for(int j=x;j<=y;j++)
int k=dinic(s,t,t+10);
// printf("k=%d\n",k);
return k==n;
}
int main()
{
while(scanf("%d%d",&n,&b)!=EOF)
{
for(int i=1;i<=n;i++)
for(int j=1;j<=b;j++)
scanf("%d",&cc[i].like[j]);
for(int i=1;i<=b;i++)
scanf("%d",&value[i]);
int l=0,r=b,mid;
while(r-l>1)
{
mid=(l+r)/2;
int flag=0;
//     printf("mid=%d\n",mid);
for(int i=1;i<=b-mid+1;i++)
{
if(init(i,i+mid-1))  { flag=1; r=mid; break;}
}
if(!flag)   l=mid;
}
printf("%d\n",r);
}
}
```

Followed by: