2047. [ZOJ2676]网络战争

★★★ 输入文件：networkwar.in 输出文件：networkwar.out 评测插件
时间限制：5 s
内存限制：32 MB

【题目描述】

Byteland的网络是由n个服务器和m条光纤组成的，每条光纤连接了两个服务器并且可以双向输送信息。这个网络中有两个特殊的服务器，一个连接到了全球的网络，一个连接到了总统府，它们的编号分别是1和N.

最近一家叫做Max Traffic的公司决定控制几条网络中的光纤，以使他们能够掌握总统府的的上网记录。为了到达这个目的，他们需要使所有从1号服务器到N号服务器的数据都经过至少一条他们所掌握的线路。

为了把这个计划付诸于行动，他们需要从这些线路的拥有者手中购买线路，每条线路都有对应的花费。自从公司的主要业务部是间谍活动而是家用宽带以后，经理就希望尽可能少的花费和尽可能高的回报。因此我们要使购买线路的平均值最小。

如果我们购买了k条线路，花费了c元，我们希望找到使c/k最小的方案。

【输入格式】

多组数据，每组数据第一行是两个整数n和m（1<=n<=100,1<=m<=400),代表服务器的个数和线路数

之后的m行，每行三个整数a，b，c，分别代表了这条线路所连接的服务器和购买这条线路的花费，花费都是正数且不会超过10^7

没有自边，没有重边，保证任意两点都是连通的。

最后一行为两个0

【输出格式】

每组数据的第一行是一个整数k，代表购买多少条线路

之后k个整数，代表购买线路的编号，编号是它们在输入文件被给处的顺序

每组数据之间有一个空行

【样例输入】

【样例输出】

4

3 4 5 6

3

1 2 3

　　可以看看2007胡博涛的论文。

 #include <iostream>

 #include <cstring>

 #include <cstdio>

 #include <queue>

 #include <cmath>

 using namespace std;

 const int maxn=;

 const int maxm=;

 const double eps=1e-;

 const int INF=;

 int n,m,e[maxm][];

 int cnt,fir[maxn],to[maxm],nxt[maxm],ID[maxm];

 double cap[maxn];

 void addedge(int a,int b,double c,int id){

     nxt[++cnt]=fir[a];

     fir[a]=cnt;

     ID[cnt]=id;

     cap[cnt]=c;

     to[cnt]=b;

 }

 queue<int>q;

 int dis[maxn];

 bool BFS(int s,int t){

     memset(dis,,sizeof(dis));

     dis[t]=;q.push(t);

     while(!q.empty()){

         int x=q.front();q.pop();

         for(int i=fir[x];i;i=nxt[i])

             if(!dis[to[i]]){

                 dis[to[i]]=dis[x]+;

                 q.push(to[i]);

             }

     }

     return dis[s];

 }

 int fron[maxn];

 int gap[maxn],path[maxn];

 double ISAP(int s,int t){

     if(!BFS(s,t))return ;

     for(int i=s;i<=t;i++)++gap[dis[i]];

     for(int i=s;i<=t;i++)fron[i]=fir[i];

     int p=s;

     double f,ret=;

     while(dis[s]<=t){

         if(p==t){

             f=INF;

             while(p!=s){

                 f=min(f,cap[path[p]]);

                 p=to[path[p]^];

             }

             ret+=f;p=t;

             while(p!=s){

                 cap[path[p]]-=f;

                 cap[path[p]^]+=f;

                 p=to[path[p]^];

             }

         }

         int &ii=fron[p];

         for(;ii;ii=nxt[ii])

             if(cap[ii]>eps&&dis[p]==dis[to[ii]]+)

                 break;

         if(ii)

             path[p=to[ii]]=ii;

         else{

             if(--gap[dis[p]]==)break;

             int minn=t+;

             for(int i=fir[p];i;i=nxt[i])

                 if(cap[i]>eps)minn=min(minn,dis[to[i]]);

             ++gap[dis[p]=minn+];ii=fir[p];

             if(p!=s)p=to[path[p]^];

         }

     }

     return ret;

 }

 int ch[maxm],ans;

 void Init(){

     memset(fir,,sizeof(fir));

     memset(gap,,sizeof(gap));

     memset(ch,,sizeof(ch));

     cnt=;

 }

 double Solve(double lam){

     Init();

     double ret=0.0;

     for(int i=;i<=m;i++){

         if(e[i][]-lam<-eps){

             ret+=e[i][]-lam;

             ch[i]=;

         }

         else{

             addedge(e[i][],e[i][],e[i][]-lam,i);

             addedge(e[i][],e[i][],e[i][]-lam,i);

         }

     }

     ret+=ISAP(,n);

     for(int i=;i<=cnt;i++)

         if(fabs(cap[i])<eps&&ID[i])ch[ID[i]]=;

     return ret;

 }

 int main(){

 #ifndef ONLINE_JUDGE

     freopen("networkwar.in","r",stdin);

     freopen("networkwar.out","w",stdout);

 #endif

     while(true){

         scanf("%d%d",&n,&m);

         if(!n&&!m)break;

         for(int i=;i<=m;i++)

             for(int j=;j<=;j++)

                 scanf("%d",&e[i][j]);

         double lo=eps,hi=INF,lam;

         for(int t=;t<=;t++){

             lam=(lo+hi)/;

             if(Solve(lam)>eps)

                 lo=lam;

             else

                 hi=lam;

             if(hi-lo<eps)break;

         }

         ans=;

         for(int i=;i<=m;i++)

             if(ch[i])ans+=;

         printf("%d\n",ans);

         for(int i=;i<=m;i++)

             if(ch[i])printf("%d ",i);

         printf("\n\n");

     }

     return ;

 }

秒客网