首页 > 代码库 > POJ 3380 最大流
POJ 3380 最大流
Description
It is year 2500 A.D. and there is a terrible war between the forces of the Earth and the Mars. Recently, the commanders of the Earth are informed by their spies that the invaders of Mars want to land some paratroopers in the m × n grid yard of one their main weapon factories in order to destroy it. In addition, the spies informed them the row and column of the places in the yard in which each paratrooper will land. Since the paratroopers are very strong and well-organized, even one of them, if survived, can complete the mission and destroy the whole factory. As a result, the defense force of the Earth must kill all of them simultaneously after their landing.
In order to accomplish this task, the defense force wants to utilize some of their most hi-tech laser guns. They can install a gun on a row (resp. column) and by firing this gun all paratroopers landed in this row (resp. column) will die. The cost of installing a gun in the ith row (resp. column) of the grid yard is ri (resp. ci ) and the total cost of constructing a system firing all guns simultaneously is equal to the product of their costs. Now, your team as a high rank defense group must select the guns that can kill all paratroopers and yield minimum total cost of constructing the firing system.
Input
Input begins with a number T showing the number of test cases and then, T test cases follow. Each test case begins with a line containing three integers 1 ≤ m ≤ 50 , 1 ≤ n ≤ 50 and 1 ≤ l ≤ 500 showing the number of rows and columns of the yard and the number of paratroopers respectively. After that, a line with m positive real numbers greater or equal to 1.0 comes where the ith number is ri and then, a line with npositive real numbers greater or equal to 1.0 comes where the ith number is ci. Finally, l lines come each containing the row and column of a paratrooper.
Output
For each test case, your program must output the minimum total cost of constructing the firing system rounded to four digits after the fraction point.
Sample Input
1 4 4 5 2.0 7.0 5.0 2.0 1.5 2.0 2.0 8.0 1 1 2 2 3 3 4 4 1 4
Sample Output
16.0000
题意：给出火星人降落的坐标（行x,列y）和使用每一行每一列武器的代价，你可以在一行或一列使用一把武器，可以消灭掉该行或该列的所有外星人。使用多种武器的代价是他们的乘积，你需要求出消灭所有火星人的最小代价。
思路：在把乘机转化成对数相加的形式，可以看到要消灭一个外星人，要么在他所在的行上放一把武器，要么在他所在列上放一把武器，因此可以在源点s和行x上连一条log(w)的边，在列和汇点t上连一条log(w)的边，在外星人的坐标x和y+n之间连一条INF的边。因为增广的时候满足流量限制所以会选择最小的代价。
不过还是wa了很久。。原因就是用个g++提交，输出的时候使用了%lf,后来改成%f了还是wa，后来发现关闭了c++和c的输入输出同步，但任然在混用输入。。取消关闭之后就ac了。。。所以建议没事还是不要混用输入输出了
代码如下：
/*************************************************************************
> File Name: c.cpp
> Author: acvcla
> QQ:
> Mail: acvcla@gmail.com
> Created Time: 2014年10月13日 星期一 22时26分17秒
************************************************************************/
#include<iostream>
#include<algorithm>
#include<cstdio>
#include<vector>
#include<cstring>
#include<map>
#include<queue>
#include<stack>
#include<string>
#include<cstdlib>
#include<ctime>
#include<set>
#include<math.h>
using namespace std;
typedef long long LL;
const int maxn = 5e2 + 30;
const int INF =1e7;
#define rep(i,a,b) for(int i=(a);i<=(b);i++)
#define pb push_back
int n,m,s,t,l;
int d[maxn],cur[maxn];
struct Edge
{
int from,to;
double cap,flow;
};
std::vector<int>G[maxn];
std::vector<Edge>edges;
void init(int n){
for(int i=0;i<=n;i++)G[i].clear();
edges.clear();
}
void addEdge(int u,int v,double w)
{
edges.pb((Edge){u,v,w,0});
edges.pb((Edge){v,u,0.0,0});
int sz=edges.size();
G[u].pb(sz-2);
G[v].pb(sz-1);
}
int bfs(){
memset(d,0,sizeof d);
queue<int>q;
q.push(s);
while(!q.empty()){
int u=q.front();q.pop();
for(int i=0;i<G[u].size();i++){
Edge &e=edges[G[u][i]];
if(e.to==s)continue;
if(!d[e.to]&&e.cap>e.flow){
q.push(e.to);
d[e.to]=d[u]+1;
}
}
}
return d[t];
}
double dfs(int u,double a)
{
if(u==t||a==0.0)return a;
double flow=0.0,f=0.0;
for(int &i=cur[u];i<G[u].size();++i){
Edge &e=edges[G[u][i]];
if(d[e.to]==d[u]+1&&(f=dfs(e.to,min(a,e.cap-e.flow)))>0.0){
e.flow+=f;
edges[G[u][i]^1].flow-=f;
flow+=f;
a-=f;
if(a==0.0)break;
}
}
return flow;
}
double Dinic(){
double flow=0;
while(bfs()){
memset(cur,0,sizeof cur);
flow+=dfs(s,INF);
}
return flow;
}
int main(){
//开启关闭同步且混用输入输出wa，注释掉AC
//ios_base::sync_with_stdio(false);
//cin.tie(0);
int T;scanf("%d",&T);
while(T--){
scanf("%d%d%d",&n,&m,&l);
int u,v;
s=0,t=n+1+m;
init(t);
double w;
for(int i=1;i<=n;i++){
cin>>w;
addEdge(s,i,log(w));
}for(int i=1;i<=m;i++){
cin>>w;
addEdge(n+i,t,log(w));
}
for(int i=1;i<=l;i++){
cin>>u>>v;
addEdge(u,v+n,INF);
}
double ans=Dinic();
printf("%.4f\n",exp(ans));
}
return 0;
}POJ 3380 最大流