欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

HDU5988 Coding Contest(费用流)

程序员文章站 2022-05-22 10:46:45
...

2016青岛现场赛的一题,由于第一次走过不会产生影响,需要拆点,不过比赛时没想到,此外还有许多细节要注意,如要加eps,时间卡得较紧要注意细节优化等

 

#include <iostream>
#include <cstring>
#include <queue>
#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <algorithm>
#include <cstring>
#include <vector>
using namespace std;
const int N = 108, M = 50000;
const int INF = 1e9;
const double eps = 1e-7;
int q[1000000];
struct Node{
	int u, v, cap;
	double cost;
	int next;
}edge[M];//有向图,u到v的容量,费用
int tot;
int head[N], pre[N], path[N];
double dis[N];
bool inq[N];

void init(){
	tot = 0;
	memset(head, -1, sizeof(head));
}

void add(int u, int v, int cap, double cost){
    edge[tot].u = u;
	edge[tot].v = v;
	edge[tot].cap = cap;
	edge[tot].cost = cost;
	edge[tot].next = head[u];
	head[u] = tot++;
	edge[tot].u = v;
	edge[tot].v = u;
	edge[tot].cap = 0;
	edge[tot].cost = -cost;
	edge[tot].next = head[v];
	head[v] = tot++;
}

bool SPFA(int st, int des){
	memset(inq, 0, sizeof(inq));
	fill(dis, dis + des + 2, INF);
	memset(pre, -1, sizeof(pre));
	int front = 0, rear = 0;
	q[rear++] = st;
	dis[st] = 0;
	inq[st] = true;
	while(front < rear){
		int u = q[front++];


		inq[u] = false;
		for(int i = head[u]; ~i; i = edge[i].next){
			int v = edge[i].v;
			if(edge[i].cap > 0 && dis[v] > dis[u] + edge[i].cost + eps){
				dis[v] = dis[u] + edge[i].cost;
				pre[v] = u;
				path[v] = i;
				if(!inq[v]){
					inq[v] = true;
					q[rear++] = v;
				}
			}
		}
	}
	return pre[des] != -1;
	//return dis[des] + eps < INF;
}

double EdmondsKarp(int st, int des){
	double mincost = 0, flow = 0;
	while(SPFA(st, des)){
		int f = INF;
		for(int i = des; i != st; i = pre[i]){
            if(f > edge[path[i]].cap){
                f = edge[path[i]].cap;
            }
		}
		for(int i = des; i != st; i = pre[i]){
			edge[path[i]].cap -= f;
			edge[path[i]^1].cap += f;
		}
		mincost += f * dis[des];
		flow += f;
	}
	return mincost;
}
int main(){
	int t;
	cin >>t;
	while(t--){
		int n, m;
		scanf("%d %d", &n, &m);
		init();
		int st = 0, des = n + 1;
		for(int i = 1; i <= n; i++){
			int si, bi;
			scanf("%d %d", &si, &bi);
			if(si > bi){
				add(st, i, si - bi, 0.0);
			}else if(si < bi){
				add(i, des, bi - si, 0.0);
			}
		}
		while(m--){
			int u, v, c;
			double p;
			scanf("%d %d %d %lf", &u, &v, &c, &p);
			if(c > 0){
                add(u, v, 1, 0);
                if(c > 1){
                    add(u, v, c - 1, -log10(1 - p));
                }
			}
		}
		printf("%.2f\n", 1.0 - pow(10.0, -EdmondsKarp(st, des)));

	}
	return 0;
}