Online JudgeProblem SetAuthorsOnline ContestsUser
Web Board
Home Page
F.A.Qs
Statistical Charts
Problems
Submit Problem
Online Status
Prob.ID:
Register
Update your info
Authors ranklist
Current Contest
Past Contests
Scheduled Contests
Award Contest
User ID:
Password:
  Register
北京大学《ACM/ICPC大学生程序设计竞赛训练》暑期课面向全球招生!

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];
void  add(int a,int b,int c)
{
      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++)
      add(s,i,1);
   for(int i=n+1;i<=n+b;i++)
      add(i,t,value[i-n]);
   for(int i=1;i<=n;i++)
      for(int j=x;j<=y;j++)
         add(i,cc[i].like[j]+n,1);
   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:

Post your reply here:
User ID:
Password:
Title:

Content:

Home Page   Go Back  To top


All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator