題解：
神題一道。。。
題解戳這裡：http://hi.baidu.com/strongoier/item/0425f0e5814e010265db0095
無限orzzzzz
1 #include<cstdio>
2
3 #include<cstdlib>
4
5 #include<cmath>
6
7 #include<cstring>
8
9 #include<algorithm>
10
11 #include<iostream>
12
13 #include<vector>
14
15 #include<map>
16
17 #include<set>
18
19 #include<queue>
20
21 #include<string>
22
23 #define inf 1000000000
24
25 #define maxn 200000+5
26
27 #define maxm 200000+5
28
29 #define eps 1e-10
30
31 #define ll long long
32
33 #define pa pair<int,int>
34
35 #define for0(i,n) for(int i=0;i<=(n);i++)
36
37 #define for1(i,n) for(int i=1;i<=(n);i++)
38
39 #define for2(i,x,y) for(int i=(x);i<=(y);i++)
40
41 #define for3(i,x,y) for(int i=(x);i>=(y);i--)
42
43 #define for4(i,x) for(int i=head[x],y;i;i=e[i].next)
44
45 #define mod 1000000007
46
47 using namespace std;
48
49 inline int read()
50
51 {
52
53 int x=0,f=1;char ch=getchar();
54
55 while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
56
57 while(ch>='0'&&ch<='9'){x=10*x+ch-'0';ch=getchar();}
58
59 return x*f;
60
61 }
62 int n,m,s,t,tot=1,head[maxn],cur[maxn],h[maxn],num[100][100];
63 double maxflow,a[100][100][3];
64 queue<int>q;
65 struct edge{int go,next;double v;}e[maxm];
66 inline void add(int x,int y,double v)
67 {
68 e[++tot]=(edge){y,head[x],v};head[x]=tot;
69 e[++tot]=(edge){x,head[y],0};head[y]=tot;
70 }
71 bool bfs()
72 {
73 for(int i=s;i<=t;i++)h[i]=-1;
74 q.push(s);h[s]=0;
75 while(!q.empty())
76 {
77 int x=q.front();q.pop();
78 for(int i=head[x];i;i=e[i].next)
79 if(e[i].v>eps&&h[e[i].go]==-1)
80 {
81 h[e[i].go]=h[x]+1;q.push(e[i].go);
82 }
83 }
84 return h[t]!=-1;
85 }
86 double dfs(int x,double f)
87 {
88 if(x==t) return f;
89 double tmp,used=0.0;
90 for(int i=cur[x];i;i=e[i].next)
91 if(e[i].v>eps&&h[e[i].go]==h[x]+1)
92 {
93 tmp=dfs(e[i].go,min(e[i].v,f-used));
94 e[i].v-=tmp;if(e[i].v>eps)cur[x]=i;
95 e[i^1].v+=tmp;used+=tmp;
96 if(fabs(used-f)<eps)return f;
97 }
98 if(used<eps) h[x]=-1;
99 return used;
100 }
101 void dinic()
102 {
103 maxflow=0.0;
104 while(bfs())
105 {
106 for (int i=s;i<=t;i++)cur[i]=head[i];maxflow+=dfs(s,inf);
107 }
108 }
109 bool check(double mid)
110 {
111 double ret=0.0;
112 memset(head,0,sizeof(head));tot=1;
113 for0(i,n+1)for0(j,m+1)
114 if(i&&i<n+1&&j&&j<m+1)add(s,num[i][j],a[i][j][0]),ret+=a[i][j][0];
115 else add(num[i][j],t,inf);
116 for0(i,n)for1(j,m)add(num[i][j],num[i+1][j],mid*a[i][j][1]),add(num[i+1][j],num[i][j],mid*a[i][j][1]);
117 for1(i,n)for0(j,m)add(num[i][j],num[i][j+1],mid*a[i][j][2]),add(num[i][j+1],num[i][j],mid*a[i][j][2]);
118 dinic();
119 return ret-maxflow>1e-9;
120 }
121
122 int main()
123
124 {
125
126 freopen("input.txt","r",stdin);
127
128 freopen("output.txt","w",stdout);
129
130 n=read();m=read();
131 for0(i,n+1)for0(j,m+1)num[i][j]=++tot;s=0;t=++tot;
132 for1(i,n)for1(j,m)a[i][j][0]=read();
133 for0(i,n)for1(j,m)a[i][j][1]=read();
134 for1(i,n)for0(j,m)a[i][j][2]=read();
135 double l=0,r=n*m*100;
136 while(r-l>1e-5)
137 {
138 double mid=(l+r)/2;
139 if(check(mid))l=mid;else r=mid;
140 }
141 printf("%.3f\n",l);
142
143 return 0;
144
145 } View Code
3232: 圈地遊戲
Time Limit: 20 Sec Memory Limit: 128 MB
Submit: 498 Solved: 248
[Submit][Status]
Description
DZY家的後院有一塊地，由N行M列的方格組成，格子内種的菜有一定的價值，并且每一條機關長度的格線有一定的費用。
DZY喜歡在地裡散步。他總是從任意一個格點出發，沿着格線行走直到回到出發點，且在行走途中不允許與已走過的路線有任何相交或觸碰（出發點除外）。記這條封閉路線内部的格子總價值為V，路線上的費用總和為C，DZY想知道V/C的最大值是多少。
Input
第一行為兩個正整數n,m。
接下來n行，每行m個非負整數，表示對應格子的價值。
接下來n+1行，每行m個正整數，表示所有橫向的格線上的費用。
接下來n行，每行m+1個正整數，表示所有縱向的格線上的費用。
（所有資料均按從左到右，從上到下的順序輸入，參見樣例和配圖）
Output
輸出一行僅含一個數，表示最大的V/C，保留3位小數。
Sample Input
3 4
1 3 3 3
1 3 1 1
3 3 1 0
100 1 1 1
97 96 1 1
1 93 92 92
1 1 90 90
98 1 99 99 1
95 1 1 1 94
1 91 1 1 89
Sample Output
1.286