Submission #2560313

---

Source Code Expand

#include <iostream>
#include <algorithm>
#include <map>
#include <math.h>
#include <stdio.h>
#include <string.h>
#include <algorithm>
#define MAXN 50050
#define MAXN_ 5050
#define INF 0x3f3f3f3f
using namespace std;
struct edge{ int to,cap,cost,rev;};
int n,m,flow,s,t,cap,res,cost,from,to;
std::vector<edge> G[MAXN_];
int dist[MAXN_],prevv[MAXN_],preve[MAXN_]; // 最短路的前驱节点 和 对应的边
inline void add()
{
  //也许你看到这里会看不懂，为什么要存一个 size 进来， 那么别急，我们下边的存反边 会用到的！
    G[from].push_back((edge){to,cap,cost,(int)G[to].size()});
    G[to].push_back((edge){from,0,-cost,(int)G[from].size()-1});
}
inline int read()
{
    int x=0;
    char c=getchar();
    bool flag=0;
    while(c<'0'||c>'9'){if(c=='-')flag=1;    c=getchar();}
    while(c>='0'&&c<='9'){x=(x<<3)+(x<<1)+c-'0';c=getchar();}
    return flag?-x:x;
}
inline void min_cost_flow(int s,int t,int f)
{
    while(f > 0)
    {
        memset(dist,INF,sizeof dist);
        dist[s] = 0;
        bool update = true;
        while(update)
        {
            update = false;
            for(int i=1;i<=n;i++)
            {
                if(dist[i] == INF) continue;
                for(int j=0;j<(int)G[i].size(); ++j)
                {
                    edge &e = G[i][j];
                    if(e.cap > 0 && dist[e.to] > dist[i] + e.cost)
                    {
                        dist[e.to] = dist[i] + e.cost;
                        prevv[e.to] = i;
                        preve[e.to] = j;
                        update = true; 
                    } 
                }
            }
        }
        // 此时的 INF 表示再也没有 增广路径，于是就是最后的答案了!
        if(dist[t] == INF) break;
        int d = f;
        for(int v = t; v != s; v = prevv[v])
            d = min(d,G[prevv[v]][preve[v]].cap);
        // d 就是 增广路的 流量！
        f -= cap;
        flow += d;
        res += d * dist[t];
        for(int v=t;v!=s;v=prevv[v])
        {
            edge &e = G[prevv[v]][preve[v]];
            e.cap -= d;
            G[v][e.rev].cap += d; // 给 反边加上适当的边权！
        }
    }
}
int main(int argc,char const* argv[])
{
   n = read(); m = read(); s = read(); t = read();
   for(int i=1;i<=m;++i)
   {
           scanf("%d%d%d%d",&from,&to,&cap,&cost);
           add();
   }
   min_cost_flow(s,t,INF);
   printf("%d %d\n",flow,res);
   return 0;
}

Submission Info

Compile Error

./Main.cpp:14:6: error: ‘vector’ in namespace ‘std’ does not name a template type
 std::vector<edge> G[MAXN_];
      ^
./Main.cpp: In function ‘void add()’:
./Main.cpp:19:5: error: ‘G’ was not declared in this scope
     G[from].push_back((edge){to,cap,cost,(int)G[to].size()});
     ^
./Main.cpp: In function ‘void min_cost_flow(int, int, int)’:
./Main.cpp:44:36: error: ‘G’ was not declared in this scope
                 for(int j=0;j<(int)G[i].size(); ++j)
                                    ^
./Main.cpp:61:23: error: ‘G’ was not declared in this scope
             d = min(d,G[prevv[v]][preve[v]].cap);
                       ^
./Main.cpp:68:23: error: ‘G’ was not declared in this scope
             edge &e = G[prevv[v]][preve[v]];
                       ^
./Main.cpp: In function ‘int main(int, const char**)’:
./Main.cpp:79:50: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
            scanf("%d%d%d%d",&from,&to,&cap,&cost);
       ...