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

大家来看看为啥我用网络流水不过去?(附代码)

Posted by 120705008 at 2014-08-12 17:17:50 on Problem 2536
#include<iostream>
using namespace std;
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<cmath>
#include<string>
#include<map>
#include<queue>
#include<algorithm>

#define MAXM 900000
#define MAXN 300
const int oo=1<<29; 

struct Dinic  
{  
      struct node   
      {  
             int x,y,c,next;  
      }line[MAXM];     
      int Lnum,_next[MAXN],dis[MAXN];  
      void initial(int n)   
      {  
             for (int i=0;i<=n;i++) _next[i]=-1;  
             Lnum=-1;  
      }   
      void addline(int x,int y,int c)  
      {  
             line[++Lnum].next=_next[x],_next[x]=Lnum;  
             line[Lnum].x=x,line[Lnum].y=y,line[Lnum].c=c;  
             line[++Lnum].next=_next[y],_next[y]=Lnum;  
             line[Lnum].x=y,line[Lnum].y=x,line[Lnum].c=0;               
      }  
      bool BFS(int s,int e)  
      {   
             queue<int> Q;  
             while (!Q.empty()) Q.pop();  
             memset(dis,0,sizeof(dis));  
             dis[s]=1;  
             Q.push(s);  
             while (!Q.empty())  
             {  
                   int h,k;  
                   h=Q.front(),Q.pop();  
                   if (h==e) return dis[e];  
                   for (k=_next[h];k!=-1;k=line[k].next)  
                      if (line[k].c && !dis[line[k].y])  
                         dis[line[k].y]=dis[h]+1,Q.push(line[k].y);                   
             }   
             return false;  
      }  
      int dfs(int x,int flow,int e)    
      {       
             if (x==e) return flow;     
             int temp,cost=0;    
             for (int k=_next[x];k!=-1;k=line[k].next)    
             if (line[k].c && dis[line[k].y]==dis[x]+1)    
             {    
                    temp=dfs(line[k].y,min(flow-cost,line[k].c),e);     
                    if (temp)    
                    {    
                           line[k].c-=temp,line[k^1].c+=temp;    
                           cost+=temp;    
                           if (flow==cost) return cost;    
                    }else dis[line[k].y]=-1;    
             }    
             return cost;    
      }    
      int MaxFlow(int s,int e)  
      {  
             int MaxFlow=0;  
             while (BFS(s,e)) 
                MaxFlow+=dfs(s,oo,e);   
             return MaxFlow;  
      }  
}T;   

double dis(int x,int y,int x1,int y1)
{
    return sqrt((x-x1)*(x-x1)+(y-y1)*(y-y1));
}

int main()
{
    int n,m,s,v;
    while (~scanf("%d%d%d%d",&n,&m,&s,&v))
          {
          int i,j;
          double a[300][2],b[300][2];
          
          for (i=1;i<=n;++i)
              scanf("%lf%lf",&a[i][0],&a[i][1]);
          for (i=1;i<=m;++i)
              scanf("%lf%lf",&b[i][0],&b[i][1]);              
          
          int distance=s*v;
          int N=n+m+1;
          T.initial(N);
          for (i=1;i<=n;++i) T.addline(0,i,1);
          for (i=1;i<=m;++i) T.addline(i+n,N,1);
          for (i=1;i<=n;++i)
              for (j=1;j<=m;++j)
                  {
                  if (distance>=dis(a[i][0],a[i][1],b[j][0],b[j][1]))
                     {
                     T.addline(i,j+n,1);                                                    
                     }
                  }
          printf("%d\n",n-T.MaxFlow(0,N));
          
          }

    return 0;
}

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