数组开的不大,应该是没有超的吧orz,还有什么情况下会全MLE呀?代码如下,大佬们不愿看代码,说说其他可能的原因也行啊orz
#include<bits/stdc++.h>
using namespace std;
const int N = 110, M = 2010;
const int INF = 0x3f3f3f3f;
int h[N], to[M], ne[M], idx;
double f[M], f_bak[M];
int q[N], level[N], cur[N];
int n, m, P, S = 1, T;
int maxflow, maxCost = -1;
void add(int x, int y, int z){
to[idx] = y, f[idx] = z, ne[idx] = h[x], h[x] = idx++;
to[idx] = x, f[idx] = 0, ne[idx] = h[y], h[y] = idx++;
}
bool bfs(){
int tt = 0, hh = 0;
memset(level, -1, sizeof level);
//源点入队
q[0] = S, level[S] = 0;
while(hh <= tt){
int now = q[hh ++];
cur[now] = h[now];
for(int i = h[now];~i;i = ne[i]){
int tv = to[i];
if(level[tv] < 0 && f[i]){ //未访问过 且 有残量
level[tv] = level[now] + 1;
q[++tt] = tv;
}
}
}
return level[T] != -1;
}
double dfs(int now, double flow){
if(now == T) return flow;
double used = 0;
for(int i = cur[now];~i;i = ne[i]){
cur[now] = i; //更新当前弧
int tv = to[i];
double tmpflow = 0;
if(level[tv] = level[now] + 1 && f[i]){ //下一层级 且有残量
if(tmpflow = dfs(tv, min(flow-used, f[i]))){
used += tmpflow;
//更新残量网络
f[i] -= tmpflow;
f[i^1] += tmpflow;
if(used == flow) break;
}
}
}
return used;
}
double dinic(){
double ans = 0;
while(bfs()){
int ff;
while(ff = dfs(S, INF)){
ans += ff;
}
}
return ans;
}
int main(){
scanf("%d%d%d", &n, &m, &P);
T = n;
memset(h, -1, sizeof h);
for(int i = 0;i < m;i ++){
int x, y, z;
scanf("%d%d%d", &x, &y, &z);
add(x, y, z);
}
for(int i = 0;i < idx;i ++) f_bak[i] = f[i];
maxflow = dinic();
printf("%.0f\n", maxflow);
double l = 0, r = 50000;
double tmpMaxflow;
while(r-l > 1e-6){
double mid = (l+r)/2.0;
for(int i = 0;i < idx;i ++) f[i] = min(f_bak[i], mid);
tmpMaxflow = dinic();
if(fabs(tmpMaxflow - maxflow) < 1e-6) r = mid; //存在满足要求的可行流时
else l = mid;
}
printf("%.4f\n", l*P);
}