http://acm.zju.edu.cn/onlinejudge/showProblem.do?problemId=1676
对顶点i,j,起点s=1,终点t=n,可以认为题意要求一组01矩阵use[i][j],使得aveCost=sigma(use[i][j]*cost[i][j])/sigma(use[i][j])最小,且{(i,j)|use[i][j]==1}是图的S-T割
定义F(e)=min(sigma(use[i][j]*(cost[i][j]-a))),明显,F(e)是目标式的变形,且当F(e)=0时,a就是aveCost,以cost[i][j]-a为容量建图,那么此时F(e)就是最小割容量.
二分确定最小割也即最大流为0时的a值,当流量恰好为0时取值最优,否则,若流量大于0不是最优,流量小于0不满足题意
注意:当确定a值时,cost[i][j]-a会导致负容量边,这些边可以使F(e)更小,所以直接加上即可
#include <cstdio>
#include <cstring>
#include<algorithm>
#include <queue>
#include <cmath>
using namespace std;
const int maxn=;
const int maxm=;
const int inf=0x7fffffff;
const double eps=1e-;
int n,m;
int G[maxn][maxn];
int e[maxn][maxn];
int len[maxn];
int num[maxn];
int ind[maxn][maxn];
double c[maxn][maxn];
double f[maxn][maxn];
int ans[maxm];
int alen;
bool pars[maxn];
int dis[maxn];
int gap[maxn]; void addedge(int f,int t){
G[f][len[f]++]=t;
G[t][len[t]++]=f;
}
double build(double lamda){
double flow=;
memset(len,,sizeof(len));
for(int i=;i<=n;i++){
for(int j=;j<num[i];j++){
int to=e[i][j];
if(i<to){
f[i][to]=c[i][to]-lamda;
f[to][i]=c[i][to]-lamda;
if(f[i][to]<){flow+=f[i][to];}
else{
addedge(i,to);
}
}
}
}
memset(dis,,sizeof(dis));
memset(gap,,sizeof(gap));
gap[]=n;
return flow;
} double dfs(int s,double flow){
if(s==n)return flow;
int mindis=n-;
double tflow=flow,sub;
for(int i=;i<len[s];i++){
int to=G[s][i];
if(f[s][to]>eps){
if(dis[to]+==dis[s]){
sub=dfs(to,min(tflow,f[s][to]));
f[s][to]-=sub;
f[to][s]+=sub;
tflow-=sub;
if(dis[]>=n)return flow-tflow;
if(tflow<eps)break;
}
mindis=min(mindis,dis[to]);
}
}
if(flow-tflow<eps){
--gap[dis[s]];
if(gap[dis[s]]==)dis[]=n;
else {
dis[s]=mindis+;
++gap[dis[s]];
}
}
return flow-tflow;
} double maxflow(double lamda){
double flow=build(lamda);
while(dis[]<n){
flow+=dfs(,inf);
}
return flow;
} double binarysearch(double s,double e){
if(s+eps>e){return s;}
double mid=(s+e)/;
double flow=maxflow(mid);
if(fabs(flow)<eps)return mid;
else if(flow<-eps){
return binarysearch(s,mid);
}
else {
return binarysearch(mid,e);
}
} void fnd(double a){
memset(pars,,sizeof(pars));
queue<int >que;
que.push();
pars[]=true;
while(!que.empty()){
int s=que.front();que.pop();
for(int i=;i<len[s];i++){
int to=G[s][i];
if(!pars[to]&&f[s][to]>eps){
pars[to]=true;que.push(to);
}
}
}
alen=;
for(int i=;i<=n;i++){
if(pars[i]){
for(int j=;j<num[i];j++){
int to=e[i][j];
if(!pars[to]){
ans[alen++]=ind[i][to];
}
else if(i<to&&c[i][to]+eps<a){
ans[alen++]=ind[i][to];
}
}
}
else {
for(int j=;j<num[i];j++){
int to=e[i][j];
if(i<to&&!pars[to]&&c[i][to]+eps<a){
ans[alen++]=ind[i][to];
}
}
}
}
sort(ans,ans+alen);
} int main(){
bool first=true;
while(scanf("%d%d",&n,&m)==){
if(!first)puts("");
else first=false;
memset(num,,sizeof(num));
int maxc=,minc=1e7+;
for(int i=;i<=m;i++){
int f,t,cost;
scanf("%d%d%d",&f,&t,&cost);
e[f][num[f]++]=t;
e[t][num[t]++]=f;
c[f][t]=c[t][f]=cost;
ind[f][t]= ind[t][f]=i;
maxc=max(maxc,cost);
minc=min(minc,cost);
}
double a=binarysearch(,maxc+);
fnd(a);
printf("%d\n",alen);
for(int i=;i<alen;i++)printf("%d%c",ans[i],i==alen-?'\n':' ');
}
return ;
}