wikioi 1035 火车停留 裸费用流

链接：http://wikioi.com/problem/1035/

怎么说呢，只能说这个建图很有意思。因为只有m条道，然后能互相接在一起的连通，对每个点进行拆点，很有意思的一道裸费用留题。

代码：

 #include <iostream>

 #include <queue>

 #include <iostream>

 #include <cstdio>

 #include <cstring>

 #include <vector>

 using namespace std;

 const int maxn = ;

 const int inf = ;

 struct node

 {

     int u,v,cap,flow,cost,next;

 }edges[];

 int head[maxn],cnt;

 void init(int n)

 {

     int i;

     for(i = ;i <= n;i++)

     head[i] = -;

     cnt = ;

     return ;

 }

 void addedge(int u,int v,int cap,int flow,int cost)

 {

     edges[cnt].u = u;

     edges[cnt].v = v;

     edges[cnt].cap = cap;

     edges[cnt].flow = flow;

     edges[cnt].cost = cost;

     edges[cnt].next = head[u];

     head[u] = cnt;

     cnt++;

     edges[cnt].u = v;

     edges[cnt].v = u;

     edges[cnt].cap = ;

     edges[cnt].flow = flow;

     edges[cnt].cost = -cost;

     edges[cnt].next = head[v];

     head[v] = cnt;

     cnt++;

 }

 int vis[maxn],a[maxn],pre[maxn],dis[maxn];

 int spfa(int s,int t,int n,int &flow,int &cost)

 {

     int i;

     queue<int> q;

     for(i = ;i <= n ;i++)

     dis[i] = -,vis[i] = ;

     dis[s] = ;

     pre[s] = ;

     vis[s] = ;

     a[s] = inf;

     int u,v;

     q.push(s);

     while(!q.empty())

     {

         u = q.front();

         q.pop();

         vis[u] = ;

         for(i = head[u];i != -;i = edges[i].next)

         {

             struct node & e = edges[i];

             v = e.v;

             if(e.cap > e.flow &&dis[v] < dis[u]+e.cost)

             {

                 dis[v] = dis[u]+e.cost;

                 a[v] = min(a[u],e.cap-e.flow);

                 pre[v] = i;

                 if(!vis[v])

                 {

                     vis[v] = ;

                     q.push(v);

                 }

             }

         }

     }

     if(dis[t] <= )

     return ;

     flow+= a[t];

     cost += dis[t]*a[t];

     u = t;

     while(u != s)

     {

         edges[pre[u]].flow += a[t];

         edges[pre[u]^].flow -= a[t];

         u = edges[pre[u]].u;

     }

     return ;

 }

 int MCMF(int s,int t,int n)

 {

     int flow = ,cost = ;

     while(spfa(s,t,n,flow,cost));

     return cost;

 }

 int r[],c[],s[];

 int main()

 {

     int n,m,u,v,i,j;

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

     init(*m);

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

         cin>>r[i]>>c[i]>>s[i];

     addedge(,*m+,n,,);

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

     {

         addedge(*m+,i,inf,,);

         addedge(i,m+i,,,c[i]);

         addedge(m+i,*m+,inf,,);

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

         {

             if(r[i]+s[i] < r[j])

             addedge(m+i,j,inf,,);

         }

     }

     double ans;

     ans = 1.0*MCMF(,*m+,*m+);

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

     return ;

 }