题目详解出自 论文 Amber-最小割模型在信息学竞赛中的应用
题目大意: 给出一个带权无向图 G = (V,E), 每条边 e属于E都有一个权值We，求一个割边集C,使得该割边集的平均边权最小，即最小化：
1.
将等式转换,引入x向量，Xi取值为(0,1),得到0-1分数规划常规式:
2.
将其转换得到一个关于的一个函数：
3.
其中为单调递减函数, 当且仅当
= 0 , 为最优值.
然后我们可以二分枚举最优值 , 然后判定当前最优值是否符合要求.
判定思路: 对于每一条边权Wi 变换成了新的边权 , 而向量X(x1,x2,..,xm)表示对应边取或者不取，所以根据其取与不取划分成一个ST集。
令取为1,则 函数就转换成了 最小割的容量了（即最大流）。
有个要注意的地方，一个是枚举的最优值是一个浮点数，还有就是当 < 0 时，必定是取得，因为它能使最优值尽可能小。
最终结果可以得出最优值后，然后在跑一次最大流，然后从源点S开始DFS标记所有可以访问到的顶点，然后求出所有取得边。注意
< 0 的边要特殊处理。因为是负值放进去计算不太方便。
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<algorithm>
#include<vector>
using namespace std; const int inf = 0x3f3f3f3f;
const int MAXN = ;
const double esp = 1e-;
int sign(double x){ return x<-esp?-:(x>esp);}
int n, m, Max;
int S, N, T; struct Edge{
int u, v, nxt;
double f;
}edge[];
struct Edge_Info{
int a,b,c;
void input(){
scanf("%d%d%d",&a,&b,&c);
}
}edge_info[];
bool vis[MAXN];
int h[MAXN], vh[MAXN];
int head[MAXN], idx; void AddEdge(int a,int b,double f){
edge[idx].u = a, edge[idx].v = b, edge[idx].f = f;
edge[idx].nxt = head[a], head[a] = idx++;
edge[idx].u = b, edge[idx].v = a, edge[idx].f = ;
edge[idx].nxt = head[b], head[b] = idx++;
}
double CreateGraph(double MaxW){
memset( head, -, sizeof(head));
idx = ;
double tmp_val = ;
for(int i = ; i <= m; i++){
int a = edge_info[i].a, b = edge_info[i].b, c = edge_info[i].c;
if( sign(c - MaxW) < )
tmp_val += c-MaxW;
else AddEdge(a,b,c-MaxW),AddEdge(b,a,c-MaxW);
}
return tmp_val;
}
double dfs(int u,double flow){
if(u == T) return flow;
int tmp = h[u]+; double sum = flow;
for(int i = head[u]; ~i; i = edge[i].nxt){
if( sign(edge[i].f) > && (h[ edge[i].v ]+ == h[u])){
double p = dfs( edge[i].v, min(sum,edge[i].f));
edge[i].f -= p, edge[i^].f += p, sum -= p;
if( sign(sum)== || h[S]==N ) return flow-sum;
}
}
for(int i = head[u]; ~i; i = edge[i].nxt ){
if( sign(edge[i].f) > ) tmp = min(tmp,h[ edge[i].v ] );
}
if( --vh[ h[u] ] == ) h[S] = N;
else ++vh[ h[u]=tmp+ ];
return flow-sum;
}
double sap(){
double maxflow = ;
memset(h,,sizeof(h));
memset(vh,,sizeof(vh));
vh[] = N;
while( h[S] < N ) maxflow += dfs( S,inf );
return maxflow;
}
double Search( double l, double r ){
while( r-l > 1e- ){
double mid = (r+l)/2.0;
double maxflow = CreateGraph( mid );
maxflow += sap();
if( sign(maxflow) < ) r = mid;
else l = mid;
}
return l;
}
void DFS(int u){
vis[u] = true;
for(int i = head[u]; ~i; i = edge[i].nxt){
if( sign(edge[i].f) > && !vis[ edge[i].v ] )
DFS( edge[i].v );
}
} vector<int> res;
int mp[MAXN][MAXN]; void solve(){
S = , T = n, N = n;
double limit = Search( , Max );
double maxflow = CreateGraph( limit );
maxflow += sap();
res.clear();
memset(vis,,sizeof(vis));
DFS(S);
for(int i = ; i <= m; i++){
mp[ edge_info[i].a ][ edge_info[i].b ] = i;
mp[ edge_info[i].b ][ edge_info[i].a ] = i;
if( sign(edge_info[i].c-limit) < )
res.push_back(i);
}
for(int i = ; i < idx; i += ){ //
int u = edge[i].u, v = edge[i].v;
if( vis[u] && !vis[v] && sign( edge[i].f ) == ){ //
res.push_back( mp[u][v] );
}
}
sort( res.begin(), res.end() );
int num = res.size();
printf("%d\n", num );
for(int i = ; i < num; i++)
printf( i==? "%d":" %d", res[i] );
printf("\n");
}
int main(){
int Case = ;
while( scanf("%d%d",&n,&m) != EOF) {
Max = ;
for(int i = ; i <= m; i++){
edge_info[i].input();
Max = max( Max, edge_info[i].c );
}
solve();
if( Case++ > ) puts("");
}
return ;
}