题意：给定无向图，每条边有权值，求该图的一个割集，是的该割集的平均边权最小
Amber的《最小割模型在信息学竞赛中的应用》中讲的很清楚了。
二分答案k，对每条边进行重新赋值为原边权-k，求最大流，
可看这里：http://hi.baidu.com/buaa_babt/item/a08fbb45599dc722fb89602a
二分枚举当前的平均边长l，对于边权<=l的直接加入当前最优割集，边权>l的将容量设为边权-l，加入到网络中，求出最小割的和sum，sum加上刚刚那些小于l的边(也是边权-l)，如果大于0就意味着l不可作为最小平均边权，小于0就可以，当等于0时直接输出即可。一定要注意精度
注意是无向图，还有就是求st割，求解答案。
#define inf 0x3f3f3f3f
#define maxm 100000
#define maxn 10000
#define eps 1e-9
struct node
{
int u ;
int v,next,id;
double w;
void init(int u1,int v1,double w1)
{
u = u1;
v = v1;
w = w1;
}
};
node e1[maxn];
int head[maxn];
int cnt ;
int cnt1;
node edge[maxn];
int sgn(double x) { //return -1 0 1
return x < -eps ? - : x > eps;
}
void init()
{
memset(head,-,sizeof(head));
cnt = ;
}
void add(int u,int v,int id,double w)
{
edge[cnt].u = u;
edge[cnt].v = v;
edge[cnt].w = w;
edge[cnt].id = id;
edge[cnt].next = head[u];
head[u] = cnt ++ ; edge[cnt].u = v;
edge[cnt].v = u;
edge[cnt].w = ;
edge[cnt].id = id;
edge[cnt].next = head[v];
head[v] = cnt ++ ;
} int dis[maxn];
int pre[maxn],cur[maxn],gap[maxn];
int s,t,nn; int sap()
{
double flow,aug;
int u;
int flag;
int i;
flow=;
aug=inf;
for(i=; i<nn; i++)
{
cur[i]=head[i];
gap[i]=;
dis[i]=;
}
gap[s]=nn;
u=s;
pre[s]=s;
while(dis[s]<nn)
{
flag=;
for(int &j=cur[u]; j!=-; j=edge[j].next)
{
//cur[u]=j;
int v=edge[j].v;
if(edge[j].w>&&dis[u]==dis[v]+)
{
flag=;
if(edge[j].w<aug)aug=edge[j].w;
pre[v]=u;
u=v;
if (u==t)
{
flow+=aug;
while(u!=s)
{
u=pre[u];
edge[cur[u]].w-=aug;
edge[cur[u]^].w+=aug;
//why?解释偶数异或1为偶数+1，奇数异或1为奇数-1，
//显然我们存的边是从0开始存的，
//所以偶数,偶数+1是残量网格中的两条边(无向边)
}
aug=inf;
}
break;
}
}
if (flag) continue;
int mindis=nn;
for(int j=head[u]; j!=-; j=edge[j].next)
{
int v=edge[j].v;
if (edge[j].w>&&dis[v]<mindis)
{
mindis=dis[v];
cur[u]=j;
}
}
if (--gap[dis[u]]==)//间隙优化
{
break;
}
dis[u]=mindis+;
gap[dis[u]]++;
u=pre[u];
}
return flow;
}
bool xxx[maxn];
int n,m;
double judge(double lda)
{
memset(xxx,,sizeof(xxx));
init();
double res = 0.0;
for(int i = ; i <= m ; i ++)
{
double tmp ;
tmp = e1[i].w - lda;
if( tmp >= )
add(e1[i].u,e1[i].v,i,tmp) , add(e1[i].v,e1[i].u,i,tmp); // 注意
else
{
res += tmp;
xxx[i] = ;
}
//if(sgn(tmp) < 0 )
// res += tmp ;
//else add(e1[i].u,e1[i].v,i,tmp);
}
s = ;
t = n ;
nn = t + ;
res += sap();
return res;
}
queue<int> q;
int col[maxn];
bool vis[maxn];
void bfs(int st,int color)
{
memset(vis,,sizeof(vis));
memset(col,,sizeof(col));
while(!q.empty()) q.pop();
q.push(st);
vis[st] = ;
col[st] = color;
while(!q.empty())
{
int u = q.front();
q.pop();
for(int i = head[u] ; i != -; i = edge[i].next)
{
int v = edge[i].v;
if(sgn(edge[i].w) > && vis[v] == )
{
vis[v] = ;
col[v] = color;
q.push(v);
}
}
}
return ;
}
vector<int> ans ;
void getst(double lda)
{
bfs(,);
ans.clear();
for(int i = ; i <= m ; i ++ ) // 注意
{
if(!xxx[i])
{
if(col[e1[i].u] != col[e1[i].v] )
{
ans.push_back(i);
}
}
else ans.push_back(i);
}
int size = ans.size();
sort(ans.begin(),ans.end());
printf("%d\n",size);
for(int i = ; i < size ; i++ )
{
printf("%d",ans[i]);
if(i != size - ) printf(" ");
else printf("\n");
}
}
int main()
{
int cas;
cas = ;
while(scanf("%d%d",&n,&m)!=EOF)
{
cnt1 = ;
int u,v;
double w;
double L,R;
L = eps;
for(int i = ; i <= m; i ++ )
{
scanf("%d%d%lf",&u,&v,&w);
e1[i].init(u,v,w);
R = max(R , w);
}
double mid ;
for(int i = ; i < ; i ++ )
// while( R - L > eps )
{
mid = ( L + R ) / 2.0;
double tmp = judge(mid);
if(sgn(tmp ) > ) // 判断
L = mid + eps;
else R = mid;
}
if(cas != ) printf("\n");
cas ++ ;
judge(L);
getst(L);
}
return ;
}