题目概述

有一个 $n$ 个点 $m$ 条双向边的图，每条边的边权是 $w_i$ 。JZ为了防止神犇之力外泄，想切断 $1$ 到 $n$ 的连接（切断一条边的代价是这条边的边权）。因为JZ是神犇，边的数量并不能限制他，所以如果选了 $k$ 条总代价为 $c$ 的边，花费是 $c\over k$ 。求最小花费时的一种可行方案。

解题报告

这是一个01分数规划的问题，所以我们先二分一个答案 $mid$ ，然后用 $w_i-mid$ 作为新边，接下来就转化为了最小割问题，只是要注意到如果一条边小于 $0$ ，则一定会被选。

任意方案怎么求？其实很简单，刷完所有增广路如果一条边的一端能够到达而另一条边不能到达，那么就说明这条边被割了。

示例程序

#include<cstdio>
#include<cstring>
#include<cmath>
#include<algorithm>
#define fr first
#define sc second
#define mp make_pair
using namespace std;
typedef long double DB;
const int maxn=100,maxm=400;

int n,m,x[maxm+5],y[maxm+5],z[maxm+5];
int E,lnk[maxn+5],son[(maxm<<2)+5],nxt[(maxm<<2)+5];
int ti,cur[maxn+5],vis[maxn+5],dis[maxn+5],que[maxn+5];
int ans[maxm+5];pair<DB,DB> e[(maxm<<2)+5];

inline int fcmp(DB a,DB b) {if (fabs(a-b)<1e-8) return 0;if (a<b) return -1;return 1;}
inline void Add(int x,int y,DB z){
    son[E]=y;nxt[E]=lnk[x];e[E]=mp(0,z);lnk[x]=E++;
    son[E]=x;nxt[E]=lnk[y];e[E]=mp(0,0);lnk[y]=E++;
    son[E]=x;nxt[E]=lnk[y];e[E]=mp(0,z);lnk[y]=E++;
    son[E]=y;nxt[E]=lnk[x];e[E]=mp(0,0);lnk[x]=E++;
}
inline bool Bfs(int s,int t){
    int Head=0,Tail=0;ti++;que[++Tail]=s;vis[s]=ti;dis[s]=0;
    while (Head!=Tail)
        for (int x=que[++Head],j=lnk[x],u;~j;j=nxt[j])
            if (vis[u=son[j]]<ti&&fcmp(e[j].fr,e[j].sc)<0)
                que[++Tail]=u,vis[u]=ti,dis[u]=dis[x]+1;
    return vis[t]==ti;
}
DB Dfs(int x,int gl,DB MIN=1e100){
    if (x==gl||!fcmp(MIN,0)) return MIN;DB f=0,now;
    for (int &j=cur[x];~j;j=nxt[j])
        if (dis[x]+1==dis[son[j]]&&fcmp(now=Dfs(son[j],gl,min(MIN,e[j].sc-e[j].fr)),0)){
            f+=now;e[j].fr+=now;e[j^1].fr-=now;
            if (!fcmp(MIN-=now,0)) break;
        }
    return f;
}
inline bool check(DB mid){
    DB ans=0;E=0;memset(lnk,255,sizeof(lnk));
    for (int i=1;i<=m;i++) if (fcmp(z[i],mid)>0) Add(x[i],y[i],z[i]-mid); else ans+=z[i]-mid;
    while (Bfs(1,n)) memcpy(cur,lnk,sizeof(lnk)),ans+=Dfs(1,n);
    return fcmp(ans,0)<=0;
}
inline void PrintEdge(DB mid,int s){
    E=0;memset(lnk,255,sizeof(lnk));ans[0]=0;
    for (int i=1;i<=m;i++) if (fcmp(z[i],mid)>0) Add(x[i],y[i],z[i]-mid);
    while (Bfs(1,n)) memcpy(cur,lnk,sizeof(lnk)),Dfs(1,n);
    for (int i=1;i<=m;i++)
        if (vis[x[i]]<ti&&vis[y[i]]==ti||vis[y[i]]<ti&&vis[x[i]]==ti||fcmp(z[i],mid)<=0) ans[++ans[0]]=i;
    printf("%d\n",ans[0]);for (int i=1;i<=ans[0];i++) {if (i>1) putchar(' ');printf("%d",ans[i]);}
}
int main(){
    freopen("program.in","r",stdin);
    freopen("program.out","w",stdout);
    while (~scanf("%d%d",&n,&m)){
        for (int i=1;i<=m;i++) scanf("%d%d%d",&x[i],&y[i],&z[i]);
            DB ans=1e100;
        for (int i=1,L=0,R=1e9;i<=n;i++,L=0,R=1e9){
            for (int mid=L+(R-L>>1);L<=R;mid=L+(R-L>>1))
                check((DB)mid/i)?R=mid-1:L=mid+1;
            if (fcmp((DB)L/i,ans)<0) ans=(DB)L/i;
        }
        PrintEdge(ans,1);puts("");
    }
    return 0;
}