ZOJ – 2676 01分数规划 浮点ISAP

题意:求最小割集$C$,使得$\frac{\sum_{i∈C} cost_i}{|C|}$最小

模型就是01分数规划$\frac{\sum_{i=1}^{m}cost_i\cdot x}{\sum_{i=1}^{m}c_i\cdot x}$,其中$c_i$恒为1,$x$为$0$或$1$

令上式为$λ$,简单变换后有$\sum_{i=1}^{m}(cost_i-1\cdot λ)x_i$,利用单调性进行二分,迭代时边的代价为$cost_i-λ$

整型模板改了下发现跑不动图,随便网上捡了个模板(`・ω・)

#include<bits/stdc++.h>
#define rep(i,j,k) for(int i = j; i <= k; i++)
#define repp(i,j,k) for(int i = j; i < k; i++)
#define rrep(i,j,k) for(int i = j; i >= k; i--)
#define erep(i,u) for(int i = head[u]; ~i; i = nxt[i])
#define scan(a) scanf("%d",&a)
#define scann(a,b) scanf("%d%d",&a,&b)
#define scannn(a,b,c) scanf("%d%d%d",&a,&b,&c)
#define println(a) printf("%d\n",a)
#define printbk(a) printf("%d ",a)
#define print(a) printf("%d",a)
using namespace std;
const int maxn = 1e3+11;
const double oo = 1e12;
const double eps = 1e-7;
typedef long long ll;
int to[maxn<<1],nxt[maxn<<1];
double cap[maxn<<1];
int head[maxn],tot;
void init(){
    memset(head,-1,sizeof head);
    tot=0;
}
void add(int u,int v,double w){
    to[tot]=v;
    nxt[tot]=head[u];
    cap[tot]=w;
//    flow[tot]=0;
    head[u]=tot++;
    swap(u,v);
    to[tot]=v;
    nxt[tot]=head[u];
    cap[tot]=w;
//    flow[tot]=0;
    head[u]=tot++;
}
int h[maxn],num[maxn],vis[maxn];
int s,t,n,m;
double aug(int u,double flow){  //   double!!!
    if(u==t) return flow;
    double l=flow;
    int tmp=n-1;
    erep(i,u){
        int v=to[i];
        if(h[u]==h[v]+1&&cap[i]>eps){
            double f=aug(v,min(l,cap[i]));
            l-=f;cap[i]-=f;cap[i^1]+=f;
            if(l<eps||h[s]==n) return flow-l;
        }
        if(cap[i]>eps&&h[v]<tmp) tmp=h[v];
    }
    if(l==flow){
        num[h[u]]--;
        if(num[h[u]]==0) h[s]=n;
        else{
            h[u]=tmp+1;
            num[h[u]]++;
        }
    }
    return flow-l;
}
double isap(){
    double ans=0;
    memset(h,0,sizeof h);
    memset(num,0,sizeof num);
    num[0]=n;
    while(h[s]<n) ans+=aug(s,oo);
    return ans;
}

void dfs(int u){
    erep(i,u){
        int v=to[i];
        if(cap[i]>eps&&!vis[v]){
            vis[v]=1;
            dfs(v);
        }
    }
}
int a[maxn],b[maxn];
double c[maxn];
bool C(double lambda){
    init();
    double ans=0;
    rep(i,1,m){
        if(c[i]-lambda<0){
            ans+=c[i]-lambda; 
        }else{
            add(a[i],b[i],c[i]-lambda);
        }
    }
    ans+=isap();
    return ans>eps;
}
int main(){
    while(cin>>n>>m){
        rep(i,1,m) cin>>a[i]>>b[i]>>c[i];
        s=1;t=n;
        double lo=0,hi=1e8,mid;
        rep(i,1,50){
            mid=(hi+lo)/2.0;
            if(C(mid)) lo=mid;
            else hi=mid;
        }
        double lambda=mid;
        memset(vis,0,sizeof vis);
        vis[s]=1; dfs(s);
        int ans=0; vector<int> vec;
        rep(i,1,m){
            if(vis[a[i]]+vis[b[i]]==1||c[i]+eps<lambda){
                ans++;
                vec.push_back(i); 
            }
        }
        println(ans);
        for(int i=0;i<vec.size();i++){
            if(i==vec.size()-1)println(vec[i]);
            else printf("%d ",vec[i]);
        }
    }
    return 0;
}

发表评论

电子邮件地址不会被公开。 必填项已用*标注