hdu5988 Coding Contest 2016青岛 费用流

大雾霾天，不想出去……
好久没写博客了，最近好懒呀……数分大物即将挂科……含参量积分简直就是噩梦……大物什么都记不得……
补了一下青岛的网络流，对图论完全无能的我只能抄题解了（还好当时没去青岛，去的北京，要不然又要打铁了……）……算是当做费用流的模板题吧……

题意：有n个节点，每个节点会有面包数和人数，如果面包不够当前节点的人吃的话就要到别的节点去，在图上走的时候，一条边第一个人不会破坏道路，但是后面的人走的时候会有几率破坏掉这条边，问所有人都吃到面包的前提下，图被破坏掉的几率有多大

题目链接

思路：正常是想到最小费用流，将所有面包多的点连向超级汇点，人多的点连向超级源，跑一下最小费用最大流。但是本题的费用是概率，不能加减，要先对概率取log,最后在乘回来，这样就能将概率进行加减了（orz，这个真的好难想到）……被剧透了这题spfa不加eps会T，也就这样吧……
一开始addedge的参数cost写成int型wa了好几次……minn的值取小了又T了一次，真的要完了……

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
#include<stdio.h>
#include<algorithm>
#include<string.h>
#include<queue>
#include<cmath>
using namespace std;
int INF=2e9;
double eps=1e-9;
struct Edge
{
	int to,next,cap,flow;
	double cost;
}edge[100005];
int head[10004],tol;
int pre[10004];
double dis[10004];
int vis[10004];
int N;
void addedge(int u,int v,int cap,double cost)
{
	edge[tol].to=v;
	edge[tol].cap=cap;
	edge[tol].cost=cost;
	edge[tol].flow=0;
	edge[tol].next=head[u];
	head[u]=tol++;
	edge[tol].to=u;
	edge[tol].cap=0;
	edge[tol].flow=0;
	edge[tol].cost=-cost;
	edge[tol].next=head[v];
	head[v]=tol++;	
}
bool spfa(int s,int t)
{
	queue<int> q;
	while(!q.empty())q.pop();
	for(int i=0;i<N;i++)
	{
		dis[i]=INF;
		vis[i]=0;
		pre[i]=-1;
	}
	dis[s]=0;
	vis[s]=1;
	q.push(s);
	while(!q.empty())
	{
		int u=q.front();
		q.pop(); 
		vis[u]=0;
		for(int i=head[u];i!=-1;i=edge[i].next)
		{
			int v=edge[i].to;
			if(edge[i].cap>edge[i].flow && dis[v]-dis[u]-edge[i].cost>eps)
			{
				dis[v]=dis[u]+edge[i].cost;
				pre[v]=i;
				if(!vis[v])
				{
					vis[v]=1;
					q.push(v);
				}
			}
			
		}
	}
	if(pre[t]==-1)return 0;
	else return 1;
}
int mcmf(int s,int t,double &cost)
{
  int flow=0;	
  cost=0;
  while(spfa(s,t))
  {
  	//printf("spfa\n");
  	int minn=INF;
  	for(int i=pre[t];i!=-1;i=pre[edge[i^1].to])
  	{
  		if(minn>edge[i].cap-edge[i].flow)
  		 minn=edge[i].cap-edge[i].flow;
	  }
	for(int i=pre[t];i!=-1;i=pre[edge[i^1].to])
	 {
	 	edge[i].flow+=minn;
	 	edge[i^1].flow-=minn;
	 	cost+=edge[i].cost*minn;
	 }   
	 flow+=minn;
  }
  return flow;
}
int a[10004],b[10004],c[10004];
int main()
{ int m,n;
	int t;
	scanf("%d",&t);
	while(t--)
	{
		memset(head,-1,sizeof(head));
		tol=0;
		scanf("%d%d",&n,&m);
		
		for(int i=1;i<=n;i++)
		{
			scanf("%d%d",&a[i],&b[i]);
			c[i]=a[i]-b[i];
		}
		N=n+10;
		for(int i=0;i<m;i++)
		{
			double cost;
			int u,v,cap;
			scanf("%d%d%d%lf",&u,&v,&cap,&cost);
		    cost=-log2(1.0-cost);
		    //printf("%f\n",cost);
		    if(cap>0)addedge(u,v,1,0.0);
		    if(cap>1)addedge(u,v,cap-1,cost);
		}
		//for(int i=0;i<5;i++)
		//printf("cost:%f\n",edge[i].cost);
		for(int i=1;i<=n;i++)
		{
			if(c[i]>0)addedge(0,i,c[i],0);
			if(c[i]<0)addedge(i,n+1,-c[i],0); 
		}
		double ans=0;
		mcmf(0,n+1,ans);
		ans=pow(2.0,-ans);
		printf("%.2f\n",1.0-ans);
	}
	return 0;
 }