HDU 2676 Network Wars 01分数规划,最小割难度:4

浏览数：29 / 时间：2015年06月09日

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)更小,所以直接加上即可

  1 #include <cstdio>
  2 #include <cstring>
  3 #include<algorithm>
  4 #include <queue>
  5 #include <cmath>
  6 using namespace std;
  7 const int maxn=103;
  8 const int maxm=403;
  9 const int inf=0x7fffffff;
 10 const double eps=1e-5;
 11 int n,m;
 12 int G[maxn][maxn];
 13 int e[maxn][maxn];
 14 int len[maxn];
 15 int num[maxn];
 16 int ind[maxn][maxn];
 17 double c[maxn][maxn];
 18 double f[maxn][maxn];
 19 int ans[maxm];
 20 int alen;
 21 bool pars[maxn];
 22 int dis[maxn];
 23 int gap[maxn];
 24 
 25 void addedge(int f,int t){
 26        G[f][len[f]++]=t;
 27        G[t][len[t]++]=f;
 28 }
 29 double build(double lamda){
 30     double flow=0;
 31     memset(len,0,sizeof(len));
 32     for(int i=1;i<=n;i++){
 33         for(int j=0;j<num[i];j++){
 34             int to=e[i][j];
 35             if(i<to){
 36                 f[i][to]=c[i][to]-lamda;
 37                 f[to][i]=c[i][to]-lamda;
 38                 if(f[i][to]<0){flow+=f[i][to];}
 39                else{
 40                 addedge(i,to);
 41                }
 42             }
 43         }
 44     }
 45     memset(dis,0,sizeof(dis));
 46     memset(gap,0,sizeof(gap));
 47     gap[0]=n;
 48     return flow;
 49 }
 50 
 51 double dfs(int s,double flow){
 52     if(s==n)return flow;
 53     int mindis=n-1;
 54     double tflow=flow,sub;
 55     for(int i=0;i<len[s];i++){
 56         int to=G[s][i];
 57         if(f[s][to]>eps){
 58         if(dis[to]+1==dis[s]){
 59             sub=dfs(to,min(tflow,f[s][to]));
 60             f[s][to]-=sub;
 61             f[to][s]+=sub;
 62             tflow-=sub;
 63             if(dis[1]>=n)return flow-tflow;
 64             if(tflow<eps)break;
 65         }
 66         mindis=min(mindis,dis[to]);
 67         }
 68     }
 69     if(flow-tflow<eps){
 70         --gap[dis[s]];
 71         if(gap[dis[s]]==0)dis[1]=n;
 72         else {
 73                 dis[s]=mindis+1;
 74                 ++gap[dis[s]];
 75         }
 76     }
 77     return flow-tflow;
 78 }
 79 
 80 double maxflow(double lamda){
 81     double flow=build(lamda);
 82     while(dis[1]<n){
 83         flow+=dfs(1,inf);
 84     }
 85     return flow;
 86 }
 87 
 88 double binarysearch(double s,double e){
 89     if(s+eps>e){return s;}
 90     double mid=(s+e)/2;
 91     double flow=maxflow(mid);
 92     if(fabs(flow)<eps)return mid;
 93     else if(flow<-eps){
 94         return binarysearch(s,mid);
 95     }
 96     else {
 97         return binarysearch(mid,e);
 98     }
 99 }
100 
101 void fnd(double a){
102     memset(pars,0,sizeof(pars));
103     queue<int >que;
104     que.push(1);
105     pars[1]=true;
106     while(!que.empty()){
107         int s=que.front();que.pop();
108         for(int i=0;i<len[s];i++){
109             int to=G[s][i];
110             if(!pars[to]&&f[s][to]>eps){
111                 pars[to]=true;que.push(to);
112             }
113         }
114     }
115     alen=0;
116     for(int i=1;i<=n;i++){
117         if(pars[i]){
118             for(int j=0;j<num[i];j++){
119                 int to=e[i][j];
120                 if(!pars[to]){
121                     ans[alen++]=ind[i][to];
122                 }
123                 else if(i<to&&c[i][to]+eps<a){
124                     ans[alen++]=ind[i][to];
125                 }
126             }
127         }
128         else {
129             for(int j=0;j<num[i];j++){
130                 int to=e[i][j];
131                 if(i<to&&!pars[to]&&c[i][to]+eps<a){
132                     ans[alen++]=ind[i][to];
133                 }
134             }
135         }
136     }
137     sort(ans,ans+alen);
138 }
139 
140 int main(){
141     bool first=true;
142     while(scanf("%d%d",&n,&m)==2){
143         if(!first)puts("");
144         else first=false;
145         memset(num,0,sizeof(num));
146         int maxc=0,minc=1e7+1;
147         for(int i=1;i<=m;i++){
148             int f,t,cost;
149             scanf("%d%d%d",&f,&t,&cost);
150             e[f][num[f]++]=t;
151             e[t][num[t]++]=f;
152             c[f][t]=c[t][f]=cost;
153             ind[f][t]= ind[t][f]=i;
154             maxc=max(maxc,cost);
155             minc=min(minc,cost);
156         }
157         double a=binarysearch(0,maxc+1);
158         fnd(a);
159         printf("%d\n",alen);
160         for(int i=0;i<alen;i++)printf("%d%c",ans[i],i==alen-1?‘\n‘:‘ ‘);
161     }
162     return 0;
163 }