Transportation

#include<stdio.h>
#include<string.h>
#include<iostream>
#include<algorithm>
#include<queue>
#include<vector>
using namespace std;
//最小费用最大流，求最大费用只需要取相反数，结果取相反数即可。
//点的总数为 N，点的编号 0~N-1
const int MAXN = 1005;
const int MAXM = 20005;
const int INF = 0x3f3f3f3f;
struct Edge
{
    int to,next,cap,flow,cost;
} edge[MAXM*4];
int head[MAXN],tol;
int pre[MAXN],dis[MAXN];
bool vis[MAXN];
int N;//节点总个数，节点编号从0~N-1
void init(int n)
{
    N = n;
    tol = 0;
    memset(head,-1,sizeof (head));
}
void addedge (int u,int v,int cap,int cost)
{
    edge[tol].to = v;
    edge[tol].cap = cap;
    edge[tol].cost = cost;
    edge[tol].flow = 0;
    edge[tol].next = head[u];
    head[u] = tol++;
    edge[tol].to = u;
    edge[tol].cap = 0;
    edge[tol].cost = -cost;
    edge[tol].flow = 0;
    edge[tol].next = head[v];
    head[v] = tol++;
}
bool spfa(int s,int t)
{
    queue<int>q;
    for(int i = 0; i < N; i++)
    {
        dis[i] = INF;
        vis[i] = false;
        pre[i] = -1;
    }
    dis[s] = 0;
    vis[s] = true;
    q.push(s);
    while(!q.empty())
    {
        int u = q.front();
        q.pop();
        vis[u] = false;
        for(int i = head[u]; i !=  -1; i = edge[i]. next)
        {
            int v = edge[i]. to;
            if(edge[i].cap > edge[i].flow &&
                    dis[v] > dis[u] + edge[i]. cost )
            {
                dis[v] = dis[u] + edge[i]. cost;
                pre[v] = i;
                if(!vis[v])
                {
                    vis[v] = true;
                    q.push(v);
                }
            }
        }
    }
    if(pre[t] == -1)return false;
    else return true;
}
//返回的是最大流，cost存的是最小费用
int minCostMaxflow(int s,int t,int &cost)
{
    int flow = 0;
    cost = 0;
    while(spfa(s,t))
    {
        int Min = INF;
        for(int i = pre[t]; i != -1; i = pre[edge[i^1].to])
        {
            if(Min > edge[i].cap - edge[i]. flow)
                Min = edge[i].cap - edge[i].flow;
        }
        for(int i = pre[t]; i != -1; i = pre[edge[i^1].to])
        {
            edge[i].flow += Min;
            edge[i^1].flow -= Min;
            cost += edge[i]. cost * Min;
        }
        flow += Min;
    }
    return flow;
}
int main(){
   int n,m,sta;
   while(scanf("%d%d%d",&n,&m,&sta)!=EOF){
       memset(pre,0,sizeof(pre));
       memset(dis,0,sizeof(dis));
       memset(vis,false,sizeof(vis));
       memset(edge,0,sizeof(edge));
      init(n+2);
      int u,v,a,c;
      for(int i=0;i<m;i++){
          scanf("%d%d%d%d",&u,&v,&a,&c);
          for(int j=0;j<c;j++)
          addedge(u,v,1,a*(2*j+1));

      }
      int ans1=0;
      addedge(0,1,sta,0);
      addedge(n,n+1,sta,0);
      int temp=minCostMaxflow(0,n+1,ans1);
      if(temp!=sta)
      puts("-1");
      else
      printf("%d\n",ans1);

   }
}

14745869

2015-09-07 20:51:51

Accepted

3667

998MS

3148K

2986 B

G++

优质内容筛选与推荐>>
1、Rockets win by the new jordans
2、Java贪食蛇小游戏 分类： java 2015-07-31 18:08 0人阅读 评论(0) 收藏
3、今日作业
4、How To Configure Server Side Transparent Application Failover [ID 460982.1]
5、QQ提醒的功能

赞赏

长按二维码向我转账

受苹果公司新规定影响，微信 iOS 版的赞赏功能被关闭，可通过二维码转账支持公众号。

阅读

好看

已推荐到看一看

你的朋友可以在“发现”-“看一看”看到你认为好看的文章。

取消 推荐

我知道了

已取消，“好看”想法已同步删除

知道了