poj 3308 Paratroopers

本文主要是介绍poj 3308 Paratroopers，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

题意：在一个矩阵中某些坐标点存在你的敌人，现有一些炮弹，他们可以摆在任意一行或者任意一列，并且可以消灭掉一行或者一列上的敌人。要求消灭掉所都敌人需要的最小花费。
最小点覆盖：
建立超级源点和每行连接，权值为放在该行炮弹的花费。
建立超级汇点和每列连接，权值为放在该列炮弹的花费。
存在敌人的行和列之间连一条边，权值为inf。
跑一遍最小割。
#include<cmath>
#include<stdio.h>
#include<string.h>
#include<iostream>
#define inf 10000000
using namespace std;
struct node{
int u,v,next;
double c;
}edge[1200];
int head[1200],pre[1200],cur[1200],dis[1200],gap[1200];
double flow[1200],a[1200],b[1200];
int T,m,n,l,x,y,e,start,end;
double ans,tot;
void add_adge(int u,int v,double c)
{
edge[e].u=u;  edge[e].v=v;  edge[e].c=c;  edge[e].next=head[u]; head[u]=e++;
edge[e].u=v;  edge[e].v=u;  edge[e].c=0;  edge[e].next=head[v]; head[v]=e++;
}
double sap()  
{   
double flow=0,aug=inf;  
bool flag; int u;
for(int i=0; i<=n+m

这篇关于poj 3308 Paratroopers的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---