程式師世界 >> 編程語言 >> C語言 >> C++ >> C++入門知識 >> poj3308 Paratroopers 二分圖的最小割

poj3308 Paratroopers 二分圖的最小割

編輯：C++入門知識

有L個傘兵空降到n*m的地圖中，告訴你傘兵的坐標，你可以在任意位置設立一個激光炮，激光炮可以花費r[i] 殺死這一行的傘兵，花費c[i]殺死這一列的傘兵，最後的

總花費是每次花費的乘積。（其實log(a)+log(b)+...+log(z)=log(a*b*...*z)，對數可以將乘法變成加法）。

對於這樣的行列模型，很容易想到二分圖，將行列看成二分圖的X和Y集，從源點到X集建邊，容量為log(r[i])，Y集到匯點建邊，容量為log(c[i])，根據傘兵的左邊從X集到Y集建邊，容量為INF（保證不選到）。這樣建圖後，原問題就變成了求最小割。

最後再用exp將答案轉回來就行了。

#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#define eps  1e-12
//#define INF   0x7fffffff
#define maxn 10000
using namespace std;
double INF=999999999.0;
int n,m,q;
int en;
int st,ed;	//源點和匯點
int dis[maxn] ;//dis[i],表示  到 原點  s 的 層數
double nn[555],mm[555];
int que[9999999];
struct edge
{
	int to,next;
	double c;
};
edge e[9999999];
int head[maxn];
void add(int a,int b,double c)
{
    c=log(c);

	e[en].to=b;
	e[en].c=c;
	e[en].next=head[a];
	head[a]=en++;
	e[en].to=a;
	e[en].c=0;
	e[en].next=head[b];
	head[b]=en++;
}
int bfs()
{
    memset(dis,-1,sizeof(dis));
    dis[st]=0;
    int front=0,rear=0;
    que[rear++]=st;
    while(front0)
            {
                dis[i] = dis[j]+ 1 ;
                que[rear++]=i;
                if(i==ed) return true;
            }
        }
    }
    return false;
}
double dfs(int x,double mx)
{
    int i,a;
    if(x==ed) return mx ;
    double ret=0;
    for(int k=head[x];k!=-1&&ret