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 ", 1.0 - pow(10.0, -EdmondsKarp(st, des))); } return 0; }