wikioi 1035 火车停留裸费用流

怎么说呢，只能说这个建图很有意思。因为只有m条道，然后能互相接在一起的连通，对每个点进行拆点，很有意思的一道裸费用留题。
代码：
  1 #include <iostream>
  2 #include <queue>
  3 #include <iostream>
  4 #include <cstdio>
  5 #include <cstring>
  6 #include <vector>
  7 using namespace std;
  8 const int maxn = 350;
  9 const int inf = 10000000;
 10 struct node
 11 {
 12     int u,v,cap,flow,cost,next;
 13 }edges[100050];
 14 int head[maxn],cnt;
 15 void init(int n)
 16 {
 17     int i;
 18     for(i = 0;i <= n;i++)
 19     head[i] = -1;
 20     cnt = 0;
 21 
 22     return ;
 23 }
 24 void addedge(int u,int v,int cap,int flow,int cost)
 25 {
 26     edges[cnt].u = u;
 27     edges[cnt].v = v;
 28     edges[cnt].cap = cap;
 29     edges[cnt].flow = flow;
 30     edges[cnt].cost = cost;
 31     edges[cnt].next = head[u];
 32     head[u] = cnt;
 33     cnt++;
 34     edges[cnt].u = v;
 35     edges[cnt].v = u;
 36     edges[cnt].cap = 0;
 37     edges[cnt].flow = flow;
 38     edges[cnt].cost = -cost;
 39     edges[cnt].next = head[v];
 40     head[v] = cnt;
 41     cnt++;
 42 }
 43 int vis[maxn],a[maxn],pre[maxn],dis[maxn];
 44 int spfa(int s,int t,int n,int &flow,int &cost)
 45 {
 46     int i;
 47     queue<int> q;
 48     for(i = 0;i <= n ;i++)
 49     dis[i] = -1,vis[i] = 0;
 50 
 51     dis[s] = 0;
 52     pre[s] = 0;
 53     vis[s] = 1;
 54     a[s] = inf;
 55 
 56     int u,v;
 57     q.push(s);
 58 
 59     while(!q.empty())
 60     {
 61         u = q.front();
 62         q.pop();
 63         vis[u] = 0;
 64 
 65         for(i = head[u];i != -1;i = edges[i].next)
 66         {
 67             struct node & e = edges[i];
 68 
 69             v = e.v;
 70             if(e.cap > e.flow &&dis[v] < dis[u]+e.cost)
 71             {
 72                 dis[v] = dis[u]+e.cost;
 73                 a[v] = min(a[u],e.cap-e.flow);
 74                 pre[v] = i;
 75                 if(!vis[v])
 76                 {
 77                     vis[v] = 1;
 78                     q.push(v);
 79                 }
 80             }
 81         }
 82     }
 83 
 84     if(dis[t] <= 0)
 85     return 0;
 86     flow+= a[t];
 87     cost += dis[t]*a[t];
 88     u = t;
 89     while(u != s)
 90     {
 91         edges[pre[u]].flow += a[t];
 92         edges[pre[u]^1].flow -= a[t];
 93         u = edges[pre[u]].u;
 94     }
 95     return 1;
 96 }
 97 int MCMF(int s,int t,int n)
 98 {
 99     int flow = 0,cost = 0;
100 
101     while(spfa(s,t,n,flow,cost));
102 
103     return cost;
104 }
105 int r[150],c[150],s[150];
106 int main()
107 {
108     int n,m,u,v,i,j;
109 
110     scanf("%d %d",&n,&m);
111     init(3*m);
112     for(i = 1;i <= m;i++)
113         cin>>r[i]>>c[i]>>s[i];
114 
115     addedge(0,2*m+1,n,0,0);
116     for(i = 1;i <= m;i++)
117     {
118         addedge(2*m+1,i,inf,0,0);
119         addedge(i,m+i,1,0,c[i]);
120         addedge(m+i,2*m+2,inf,0,0);
121         for(j = 1;j <= m;j++)
122         {
123             if(r[i]+s[i] < r[j])
124             addedge(m+i,j,inf,0,0);
125         }
126     }
127     double ans;
128     ans = 1.0*MCMF(0,2*m+2,2*m+3);
129 
130     printf("%.2f
",ans/100);
131     return 0;
132 }
View Code
wikioi 1035 火车停留 裸费用流

wikioi 1035 火车停留裸费用流
