zoj 2676 dinic模板求实型最小割（可做dinic模板）

#include<stdio.h>

#include<string.h>

#include<stdlib.h>

#include<queue>

#include<math.h>

using namespace std;

#define eps 1e-6

#define inf 0x3fffffff

#define N 410

struct node

{

    int u,v,next;

    double w;

}bian[N*4],f[N];

int yong,head[N],dis[N],work[N];

void init()

{

    yong=0;

    memset(head,-1,sizeof(head));

}

void addedge(int u,int v,double w)

{

    bian[yong].v=v;

    bian[yong].w=w;

    bian[yong].next=head[u];

    head[u]=yong++;

}

int bfs(int S,int T)

{

    queue<int>q;

    memset(dis,-1,sizeof(dis));

    dis[S]=0;

    q.push(S);

    while(!q.empty())

    {

        int u=q.front();

        q.pop();

        for(int i=head[u];i!=-1;i=bian[i].next)

        {

            int v=bian[i].v;

            if(bian[i].w>0&&dis[v]==-1)

            {

                dis[v]=dis[u]+1;

                if(v==T)

                    return 1;

                q.push(v);

            }

        }

    }

    return 0;

}

double dfs(int S,double a,int T)

{

    if(S==T)return a;

    for(int &i=work[S];i!=-1;i=bian[i].next)

    {

        int v=bian[i].v;

        if(bian[i].w>0&&dis[v]==dis[S]+1)

        {

            double tt=dfs(v,min(a,bian[i].w),T);

            if(tt>0)

            {

                bian[i].w-=tt;

                bian[i^1].w+=tt;

                return tt;

            }

        }

    }

    return 0;

}

double Dinic(int S,int T)

{

    double ans=0;

    while(bfs(S,T))

    {

        memcpy(work,head,sizeof(head));

        while(1) {

        double tt=dfs(S,inf,T);//割出来的可能是负值

         if(tt<eps)break;

            ans+=tt;

        }

    }

    return ans;

}

int a[N],len,vis[N];

void dfss(int u) {

  int i;

  // printf("%d\n",u);

  for(i=head[u];i!=-1;i=bian[i].next) {

    int v=bian[i].v;

    if(bian[i].w>eps&&!vis[v]) {

        vis[v]=1;

        dfss(v);

    }

  }

}

int main()

{

    int n,m,i;

    double st,en,mid,flow;

    while(scanf("%d%d",&n,&m)!=EOF)

    {

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

            scanf("%d%d%lf",&f[i].u,&f[i].v,&f[i].w);

        st=0;

        en=10000001;

        while(st<en+eps)

        {

            mid=(st+en)/2;

            init();

            flow=0;

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

            {

             //   printf("%.2f %.2f\n",f[i].w,mid);

                if(f[i].w<mid+eps)

                    flow=flow+f[i].w-mid;

                else

                {

                    addedge(f[i].u,f[i].v,f[i].w-mid);

                    addedge(f[i].v,f[i].u,f[i].w-mid);

                }

            }

            double k=Dinic(1,n);

            flow+=k;

      //  printf("%.2f\n",k);

            if(flow>eps)

                st=mid+eps;

            else

                en=mid-eps;

        }

  //      printf("mid=%.10f\n",mid);

        memset(vis,0,sizeof(vis));

        vis[1]=1;

        dfss(1);

        len=0;

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

          //  printf("%.10f %.10f\n",f[i].w,mid+eps);//&&vis[f[i].u]+vis[f[i].v]==1

            if(vis[f[i].u]+vis[f[i].v]==1||f[i].w<eps+mid)

                len++;

            }

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

            int ok=0;

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

            if(vis[f[i].u]+vis[f[i].v]==1||f[i].w<mid+eps) {

                    if(ok)

                    printf(" ");

                printf("%d",i);

            ok=1;

            }

            printf("\n");

            }

    return 0;

}