首页 > 代码库 > HDU 4183 Pahom on Water（最大流）
HDU 4183 Pahom on Water（最大流）
https://vjudge.net/problem/HDU-4183
题意：
这道题目的英文实在是很难理解啊。
给出n个圆，每个圆有频率，x、y轴和半径r4个属性，每次将频率为400的圆作为起点，频率为789点作为终点。从源点到汇点时必须从频率小的到频率大的，而从汇点到源点时必须从频率大的到频率小的。前提时这两个圆必须严格相交。每个点只能走一次。判断是否能从起点出发到达终点，并再次返回起点。
思路：
其实就是判断最大流是否大于等于2。因为每个点只能走一次，用拆点法。
1 #include<iostream> 2 #include<cstdio> 3 #include<cmath> 4 #include<cstring> 5 #include<queue> 6 using namespace std; 7 8 const int maxn=1000+5; 9 const int INF=0x3f3f3f3f; 10 11 struct Point 12 { 13 double p; 14 int x,y,r; 15 }point[maxn],s,t; 16 17 bool cacl(Point a,Point b) 18 { 19 double l1=(b.y-a.y)*(b.y-a.y)+(b.x-a.x)*(b.x-a.x); 20 double l2=(double)(a.r+b.r)*(a.r+b.r); 21 if(l1<l2) return true; 22 else return false; 23 } 24 25 struct Edge 26 { 27 int from,to,cap,flow; 28 Edge(int u,int v,int w,int f):from(u),to(v),cap(w),flow(f){} 29 }; 30 31 struct Dinic 32 { 33 int n,m,s,t; 34 vector<Edge> edges; 35 vector<int> G[maxn]; 36 bool vis[maxn]; 37 int cur[maxn]; 38 int d[maxn]; 39 40 void init(int n) 41 { 42 this->n=n; 43 for(int i=0;i<n;++i) G[i].clear(); 44 edges.clear(); 45 } 46 47 void AddEdge(int from,int to,int cap) 48 { 49 edges.push_back( Edge(from,to,cap,0) ); 50 edges.push_back( Edge(to,from,0,0) ); 51 m=edges.size(); 52 G[from].push_back(m-2); 53 G[to].push_back(m-1); 54 } 55 56 bool BFS() 57 { 58 queue<int> Q; 59 memset(vis,0,sizeof(vis)); 60 vis[s]=true; 61 d[s]=0; 62 Q.push(s); 63 while(!Q.empty()) 64 { 65 int x=Q.front(); Q.pop(); 66 for(int i=0;i<G[x].size();++i) 67 { 68 Edge& e=edges[G[x][i]]; 69 if(!vis[e.to] && e.cap>e.flow) 70 { 71 vis[e.to]=true; 72 d[e.to]=d[x]+1; 73 Q.push(e.to); 74 } 75 } 76 } 77 return vis[t]; 78 } 79 80 int DFS(int x,int a) 81 { 82 if(x==t || a==0) return a; 83 int flow=0, f; 84 for(int &i=cur[x];i<G[x].size();++i) 85 { 86 Edge &e=edges[G[x][i]]; 87 if(d[e.to]==d[x]+1 && (f=DFS(e.to,min(a,e.cap-e.flow) ) )>0) 88 { 89 e.flow +=f; 90 edges[G[x][i]^1].flow -=f; 91 flow +=f; 92 a -=f; 93 if(a==0) break; 94 } 95 } 96 return flow; 97 } 98 99 int Maxflow(int s,int t)100 {101 this->s=s; this->t=t;102 int flow=0;103 while(BFS())104 {105 memset(cur,0,sizeof(cur));106 flow +=DFS(s,INF);107 }108 return flow;109 }110 }DC;111 112 int n;113 114 int main()115 {116 //freopen("D:\\input.txt","r",stdin);117 int T;118 scanf("%d",&T);119 while(T--)120 {121 scanf("%d",&n);122 DC.init(2*n+10);123 for(int i=1;i<=n;i++)124 {125 scanf("%lf%d%d%d",&point[i].p,&point[i].x,&point[i].y,&point[i].r);126 if(point[i].p==400)127 {128 s=point[i];129 i--;130 n--;131 }132 else if(point[i].p==789)133 {134 t=point[i];135 i--;136 n--;137 }138 }139 140 if(cacl(s,t))141 {142 printf("Game is VALID\n");143 continue;144 }145 146 for(int i=1;i<=n;i++)147 {148 DC.AddEdge(i,n+i,1); //拆点149 if(cacl(s,point[i]) && s.p<point[i].p) DC.AddEdge(0,i,1);150 if(cacl(point[i],t) && point[i].p<t.p) DC.AddEdge(n+i,2*n+1,1);151 for(int j=1;j<=n;j++)152 {153 if(i==j) continue;154 if(cacl(point[i],point[j]) && point[i].p<point[j].p)155 DC.AddEdge(n+i,j,1);156 }157 }158 int ans=DC.Maxflow(0,2*n+1);159 if(ans>=2) printf("Game is VALID\n");160 else printf("Game is NOT VALID\n");161 }162 return 0;163 }
HDU 4183 Pahom on Water（最大流）
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。