Online Judge | Problem Set | Authors | Online Contests | User | ||||||
---|---|---|---|---|---|---|---|---|---|---|
Web Board Home Page F.A.Qs Statistical Charts | Current Contest Past Contests Scheduled Contests Award Contest |
大家来看看为啥我用网络流水不过去?(附代码)#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: |
All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator