2279. 网络战争

2279. 网络战争
二分求那个平均值、
如果比平均值小，那肯定要算上，其他没有算上的边，跑一个最小流就可以了。
也就是取出一些边之后，然后求出必须要拿出来的边。

#include <bits/stdc++.h>
using namespace std;
const int N=110,M=1e6+5,inf=1e9;
const double eps=1e-6;

int h[N],ne[M],e[M],w[M],tot=1;
void add(int from,int to,int wi) {
    e[++tot]=to;  w[tot]=wi;  ne[tot]=h[from];  h[from]=tot;
    e[++tot]=from;w[tot]=0;   ne[tot]=h[to];    h[to]=tot;
}

double wf[M];
int n,m,S,T;
int dep[N],cur[N];
bool bfs() {
    memcpy(cur,h,sizeof(h));
    memset(dep,0,sizeof(dep));
    queue<int>q;
    dep[S]=1;
    q.push(S);
    while(!q.empty()) {
        int now=q.front();
        q.pop();
        for(int i=h[now];i;i=ne[i]) {
            int to=e[i];
            if(dep[to]==0&&wf[i]>0)
                dep[to]=dep[now]+1,q.push(to);
        }
    }
    return dep[T];
}

double dfs(int now,double sum) {
    if(now==T)return sum;
    double ans=0;
    for(int i=cur[now];i&&sum;i=ne[i]) {
        cur[now]=i;
        int to=e[i];
        if(dep[to]==dep[now]+1&&wf[i]>0) {
            double k=dfs(to,min(sum,wf[i]));
            if(k<eps)dep[to]=0;
            wf[i]-=k;
            wf[i^1]+=k;
            sum-=k;
            ans+=k;
        }
    }
    return ans;
}

//也就是选出一些边，使得权值的平均值变小
double dinic(double mid) {
    double ans=0;
    for(int i=2;i<=tot;i+=2) {
        if(w[i]<=mid) {
            ans+=w[i]-mid;
            wf[i]=wf[i^1]=0;
        }
        else wf[i]=wf[i^1]=w[i]-mid;
    }
    while(bfs())ans+=dfs(S,inf);
    return ans;
}

int main() {
    cin>>n>>m>>S>>T;
    while(m--) {
        int a,b,c;
        cin>>a>>b>>c;
        add(a,b,c);
    }
    double l=0,r=1e7;
    while(r-l>eps) {
        double mid=(l+r)/2;
        if(dinic(mid)>0)l=mid;//大于0，不满足条件，往上跑
        else r=mid;//否则，往下跑
    }
    printf("%.2lf\n",r);
    return 0;
}