题目：http://www.lydsy.com/JudgeOnline/problem.php?id=2542
用类似最小费用增广路的方法去查找增广路就行啦~
代码(很丑勿喷)：
/**************************************************************
Problem: 2542
User: *****
Language: C++
Result: Accepted
Time:140 ms
Memory:2468 kb
****************************************************************/
#include <algorithm>
#include <cstring>
#include <queue>
#include <cstdio>
#include <vector>
using namespace std;
#define MAXN 500
const double detail=0.999999999999;
int n,k;
double as[MAXN];
int am[MAXN];
struct node {
int t,v;
double c;
node *next,*next0;
};
node *map[MAXN][MAXN];
node *head[MAXN];
int Insert(int s,int t,int f,double c){
if (map[s][t]==NULL){
node *p=new(node);
(*p).t=t;
(*p).c=c;
(*p).v=f;
(*p).next0=NULL;
(*p).next=head[s];
head[s]=p;
map[s][t]=p;
} else {
node *p=map[s][t];
while (p!=NULL){
if ((*p).c==c){
(*p).v+=f;
return 0;
}
p=(*p).next0;
}
p=new(node);
(*p).t=t;
(*p).v=f;
(*p).c=c;
(*p).next=head[s];
head[s]=p;
(*p).next0=map[s][t];
map[s][t]=p;
}
return 0;
}
double dist[MAXN],minc[MAXN];
int suff[MAXN],minf[MAXN];
bool f[MAXN];
int max_flow=0;
struct cmp{
bool operator()(int x, int y){
return dist[x]<dist[y];
}
};
priority_queue<int,vector<int>,cmp>qu;
double EXP(double x,int y){
if (y==1) return x;
return EXP(x,y/2)*EXP(x,y-(y/2));
}
double minimum_cost_flow(int s,int t){
double rec=1;
while (1){
memset(dist,0,sizeof(dist));
memset(f,false,sizeof(f));
f[s]=true;
dist[s]=1;
suff[s]=0;
minf[s]=0x7fffffff;
qu.push(s);
while (!qu.empty()){
int u=qu.top();
qu.pop();
if (f[u]){
f[u]=false;
node *p=head[u];
while (p!=NULL){
if ((*p).v>0&&dist[u]*(*p).c>dist[(*p).t]){
dist[(*p).t]=dist[u]*(*p).c;
suff[(*p).t]=u;
f[(*p).t]=true;
qu.push((*p).t);
minf[(*p).t]=min(minf[u],(*p).v);
minc[(*p).t]=(*p).c;
}
p=(*p).next;
}
}
}
if (dist[t]){
max_flow+=minf[t];
int i=t;
while (suff[i]){
rec*=EXP(minc[i],minf[t]);
Insert(suff[i],i,-minf[t],minc[i]);
Insert(i,suff[i],minf[t],double(1)/double(minc[i])*detail);
i=suff[i];
}
} else break;
}
return rec;
}
void output_double(double x,int y){
int i=0,l=0;
int ans[15];
ans[0]=0;
while (1){
x*=10;
int z=int(x);
x-=int(x);
ans[++l]=z;
if (z||i) i++;
if (i>=y+1) break;
}
if (ans[l]>=5) ans[l-1]++;
int j=l-1;
while (ans[j]>=10) {
ans[j-1]+=ans[j]/10;
ans[j]%=10;
j--;
}
printf("%d.",ans[0]);
for (int i=0;i++<l-1;) printf("%d",ans[i]);
printf("\n");
}
int main(){
scanf("%d%d",&n,&k);
for (int i=0;i<MAXN;i++){
head[i]=NULL;
for (int j=0;j<MAXN;j++){
map[i][j]=NULL;
}
}
for (int i=0;i++<n;) {
scanf("%lf",&as[i]);
}
for (int i=0;i++<n;) {
scanf("%d",&am[i]);
if (am[i]){
Insert(n+1,i,am[i],as[i]);
}
}
for (int i=0;i++<n;){
int x;
scanf("%d",&x);
if (x){
Insert(i,n+2,0x7fffffff,1);
}
}
while (1){
int x,y,m;
double s;
scanf("%d%d",&x,&y);
if (x==-1&&y==-1) break;
scanf("%lf%d",&s,&m);
Insert(x,y,m,s);
Insert(y,x,m,s);
}
Insert(n+3,n+1,k,1);
double ans=minimum_cost_flow(n+3,n+2);
if (max_flow<k) printf("0\n");
else output_double(ans,5);
return 0;
}
