题解

40 条题解

  • 3
    @ 2013-12-29 14:57:45

    P121380人环游世界 非上下界费用流解法:
    首先把每个点拆成两个,分别表示来源跟去向,用wi,ui表示,那么由于每个点会有vi个人经过,那么连边(S,wi,vi,0),(ui,T,vi,0)((u,v,f,c)表示从u连边到v,流量f,费用c),那么对于每条费用为pi的航线(s,t)就有连边(ws,ut,inf,pi),又由于有些人可以直接在某个城市出发,那么另加一个点k,连边(S,k,m,0),对于每个城市i,连边(k,ui,inf,0),然后跑一次最小费用最大流,那么mincost就是答案了。。。(这算是经典模型了吧。。。)
    zkw费用流写渣了。。。好慢好慢:

    编译成功

    测试数据 #0: Accepted, time = 78 ms, mem = 952 KiB, score = 10
    测试数据 #1: Accepted, time = 78 ms, mem = 956 KiB, score = 10
    测试数据 #2: Accepted, time = 0 ms, mem = 504 KiB, score = 10
    测试数据 #3: Accepted, time = 78 ms, mem = 952 KiB, score = 10
    测试数据 #4: Accepted, time = 0 ms, mem = 508 KiB, score = 10
    测试数据 #5: Accepted, time = 62 ms, mem = 956 KiB, score = 10
    测试数据 #6: Accepted, time = 93 ms, mem = 952 KiB, score = 10
    测试数据 #7: Accepted, time = 109 ms, mem = 956 KiB, score = 10
    测试数据 #8: Accepted, time = 109 ms, mem = 952 KiB, score = 10
    测试数据 #9: Accepted, time = 93 ms, mem = 952 KiB, score = 10
    Accepted, time = 700 ms, mem = 956 KiB, score = 100

    #include <cstdio>
    #include <algorithm>
    #include <cstring>

    using namespace std ;

    #define MAXN 210
    #define inf 0x7fffffff

    struct network {

    int S , T ;

    struct edge {
    edge *next , *pair ;
    int t , f , c ;
    } *head[ MAXN ] ;

    network( ) {
    memset( head , 0 , sizeof( head ) ) ;
    }

    void Add( int s , int t , int f , int c ) {
    edge *p = new( edge ) ;
    p -> t = t , p -> f = f , p -> c = c , p -> next = head[ s ] ;
    head[ s ] = p ;
    }

    void AddEdge( int s , int t , int f , int c ) {
    Add( s , t , f , c ) , Add( t , s , 0 , - c ) ;
    head[ s ] -> pair = head[ t ] , head[ t ] -> pair = head[ s ] ;
    }

    int dist[ MAXN ] , slack[ MAXN ] , cost ;
    bool f[ MAXN ] ;

    int aug( int v , int flow ) {
    if ( v == T ) {
    cost += flow * dist[ S ] ;
    return flow ;
    }
    f[ v ] = true ;
    int rec = 0 ;
    for ( edge *p = head[ v ] ; p ; p = p -> next ) if ( p -> f && ! f[ p -> t ] ) {
    if ( dist[ v ] == dist[ p -> t ] + p -> c ) {
    int ret = aug( p -> t , min( flow - rec , p -> f ) ) ;
    p -> f -= ret , p -> pair -> f += ret ;
    if ( ( rec += ret ) == flow ) return flow ;
    } else slack[ p -> t ] = min( slack[ p -> t ] , dist[ p -> t ] + p -> c - dist[ v ] ) ;
    }
    return rec ;
    }

    bool relabel( ) {
    int delta = inf ;
    for ( int i = 0 ; i ++ < T ; ) if ( ! f[ i ] ) delta = min( delta , slack[ i ] ) ;
    if ( delta == inf ) return false ;
    for ( int i = 0 ; i ++ < T ; ) if ( f[ i ] ) dist[ i ] += delta ;
    return true ;
    }

    int costflow( ) {
    cost = 0 ;
    memset( dist , 0 , sizeof( dist ) ) ;
    do {
    for ( int i = 0 ; i ++ < T ; ) slack[ i ] = inf ;
    do {
    memset( f , false , sizeof( f ) ) ;
    } while ( aug( S , inf ) ) ;
    } while ( relabel( ) ) ;
    return cost ;
    }

    } net ;

    int n , m , v[ MAXN ][ 2 ] , V = 0 ;

    int main( ) {
    scanf( "%d%d" , &n , &m ) ;
    for ( int i = 0 ; i ++ < n ; ) v[ i ][ 0 ] = ++ V , v[ i ][ 1 ] = ++ V ;
    ++ V ; net.S = ++ V ; net.T = ++ V ;
    net.AddEdge( net.S , V - 2 , m , 0 ) ;
    for ( int i = 0 ; i ++ < n ; ) {
    int x ; scanf( "%d" , &x ) ;
    net.AddEdge( net.S , v[ i ][ 0 ] , x , 0 ) ;
    net.AddEdge( v[ i ][ 1 ] , net.T , x , 0 ) ;
    net.AddEdge( V - 2 , v[ i ][ 1 ] , inf , 0 ) ;
    }
    for ( int i = 0 ; i ++ < n - 1 ; ) {
    for ( int j = i ; j ++ < n ; ) {
    int x ; scanf( "%d" , &x ) ;
    if ( x != -1 ) {
    net.AddEdge( v[ i ][ 0 ] , v[ j ][ 1 ] , inf , x ) ;
    }
    }
    }
    printf( "%d\n" , net.costflow( ) ) ;
    return 0 ;
    }

  • 1
    @ 2017-07-15 16:51:56
    #include <cmath>
    #include <cstdio>
    #include <cstdlib>
    #include <cstring>
    #include <iomanip>
    #include <algorithm>
    #include <vector>
    #include <deque>
    #include <limits>
    #include <string>
    #include <sstream>
    using namespace std;
    
    const int oo_min=0xcfcfcfcf,oo_max=0x3f3f3f3f;
    
    int n,m;
    vector<int> f;
    vector<int> e;
    vector<int> u;
    vector<int> pre;
    vector<int> vis;
    vector<vector<int> > c;
    vector<vector<int> > p;
    vector<vector<int> > ce;
    vector<vector<int> > cw;
    deque<int> q;
    
    void add_edge_1(int x,int y,int c_v,int p_v)
    {
        cw[x].push_back(y);
        c[x].push_back(c_v);
        p[x].push_back(p_v);
        ce[y].push_back(cw[x].size()-1);
        cw[y].push_back(x);
        c[y].push_back(0);
        p[y].push_back(-p_v);
        ce[x].push_back(cw[y].size()-1);
    }
    
    int bfs_1(int s,int t,int *flow,int *cost)
    {
        f.resize(0);
        f.resize(cw.size(),0);
        f[s]=oo_max;
        e.resize(0);
        e.resize(cw.size(),-1);
        u.resize(0);
        u.resize(cw.size(),oo_max);
        u[s]=0;
        pre.resize(0);
        pre.resize(cw.size(),-1);
        pre[s]=s;
        vis.resize(0);
        vis.resize(cw.size(),0);
        for (q.resize(0),vis[s]=1,q.push_back(s);(!q.empty());vis[q.front()]=0,q.pop_front())
        {
            int now=q.front();
            for (int i=0;i<cw[now].size();i++)
                if (c[now][i]&&u[now]+p[now][i]<u[cw[now][i]])
                {
                    f[cw[now][i]]=min(c[now][i],f[now]);
                    e[cw[now][i]]=i;
                    u[cw[now][i]]=u[now]+p[now][i];
                    pre[cw[now][i]]=now;
                    if (vis[cw[now][i]]==0)
                        vis[cw[now][i]]=1,q.push_back(cw[now][i]);
                }
        }
        (*flow)=f[t];
        (*cost)=u[t];
        return (pre[t]!=-1);
    }
    
    void min_cost_max_flow_1(int s,int t,int *flow,int *cost)
    {
        int temp_flow,temp_cost;
        while (bfs_1(s,t,&temp_flow,&temp_cost))
        {
            for (int i=t;i!=s;i=pre[i])
                c[pre[i]][e[i]]-=temp_flow,c[i][ce[pre[i]][e[i]]]+=temp_flow;
            (*flow)+=temp_flow;
            (*cost)+=(temp_flow*temp_cost);
        }
    }
    
    int main()
    {
        
        while (~scanf("%d%d",&n,&m))
        {
            cw.resize(0);
            cw.resize(2*n+3);
            ce.resize(0);
            ce.resize(cw.size());
            c.resize(0);
            c.resize(cw.size());
            p.resize(0);
            p.resize(cw.size());
            for (int i=0;i<cw.size();i++)
            {
                cw[i].resize(0);
                ce[i].resize(0);
                c[i].resize(0);
                p[i].resize(0);
            }
            add_edge_1(0,c.size()-2,m,0);
            for (int i=1;i<=n;i++)
            {
                int v;
                scanf("%d",&v);
                add_edge_1(0,i,v,0);
                add_edge_1(i+n,cw.size()-1,v,0);
                add_edge_1(cw.size()-2,i+n,oo_max,0);
            }
            for (int i=1;i<=n-1;i++)
                for (int j=1;j<=n-i;j++)
                {
                    int cost;
                    scanf("%d",&cost);
                    if (cost!=-1)
                        add_edge_1(i,i+j+n,oo_max,cost);
                }
            int ans_flow=0,ans_cost=0;
            min_cost_max_flow_1(0,c.size()-1,&ans_flow,&ans_cost);
            printf("%d\n",ans_cost);
        }
    }
    
    • @ 2017-07-15 17:13:03

      状态 耗时 内存占用
      #1 Accepted 11ms 636.0KiB
      #2 Accepted 15ms 512.0KiB
      #3 Accepted 3ms 324.0KiB
      #4 Accepted 22ms 600.0KiB
      #5 Accepted 4ms 256.0KiB
      #6 Accepted 22ms 512.0KiB
      #7 Accepted 24ms 512.0KiB
      #8 Accepted 41ms 724.0KiB
      #9 Accepted 54ms 612.0KiB
      #10 Accepted 57ms 616.0KiB
      分数 100
      总耗时 257ms
      峰值内存 724.0KiB

  • 0
    @ 2017-01-04 14:38:55

    测试数据 #0: Accepted, time = 31 ms, mem = 1240 KiB, score = 10
    测试数据 #1: Accepted, time = 31 ms, mem = 1244 KiB, score = 10
    测试数据 #2: Accepted, time = 0 ms, mem = 668 KiB, score = 10
    测试数据 #3: Accepted, time = 31 ms, mem = 1240 KiB, score = 10
    测试数据 #4: Accepted, time = 0 ms, mem = 668 KiB, score = 10
    测试数据 #5: Accepted, time = 46 ms, mem = 1240 KiB, score = 10
    测试数据 #6: Accepted, time = 46 ms, mem = 1240 KiB, score = 10
    测试数据 #7: Accepted, time = 62 ms, mem = 1240 KiB, score = 10
    测试数据 #8: Accepted, time = 93 ms, mem = 1240 KiB, score = 10
    测试数据 #9: Accepted, time = 93 ms, mem = 1240 KiB, score = 10
    Accepted, time = 433 ms, mem = 1244 KiB, score = 100

    借用了楼下绿色的云的建图方法,对这些建模的方法的理解越来越快了,果然在草稿纸上画一下很容易理解啊。。
    要加油,争取自己也能想出这样的建模方法

    代码
    ```c++
    #include<iostream>
    #include<iomanip>
    #include<cstring>
    #include<vector>
    #include<sstream>
    #include<algorithm>
    #include<string>
    #include<cstdio>
    #include<math.h>
    #include<map>
    #include<cctype>
    #include<queue>
    #include<functional>
    #include<set>
    #define Mem(a,b) memset((a),(b),sizeof((a)))
    #define Sy system("pause")
    const int maxn = 1000;
    const int INF = 0x3f3f3f;
    using namespace std;

    struct MCMF{

    struct Edge
    {
    int from, to, cap, flow, cost;
    Edge(int a, int b, int c, int d, int e) :from(a), to(b), cap(c), flow(d), cost(e) {}
    Edge(){}
    };
    int n, m;
    vector<Edge> edges;
    vector<int> G[maxn];
    int inq[maxn], d[maxn], p[maxn], a[maxn];

    void init(int n){
    this->n = n;
    for (int i = 0; i < n; i += 1)G[i].clear(); edges.clear();
    }

    void AddEdge(int from, int to, int cap, int cost){
    edges.push_back(Edge(from, to, cap, 0, cost));
    edges.push_back(Edge(to, from, 0, 0, -cost));
    m = edges.size();
    G[from].push_back(m - 2);
    G[to].push_back(m - 1);
    }

    bool BellmanFord(int s, int t, int & flow, int & cost){
    for (int i = 0; i < n; i += 1) d[i] = INF;
    memset(inq, 0, sizeof(inq));
    d[s] = 0; inq[s] = 1; p[s] = 0; a[s] = INF;
    queue<int> Q;
    Q.push(s);
    while (!Q.empty())
    {
    int u = Q.front(); Q.pop();
    inq[u] = 0;
    for (int i = 0; i < G[u].size(); i += 1){
    Edge & e = edges[G[u][i]];
    if (e.cap > e.flow && d[e.to] > d[u] + e.cost){
    d[e.to] = d[u] + e.cost;
    p[e.to] = G[u][i];
    a[e.to] = min(a[u], e.cap - e.flow);
    if (!inq[e.to]){
    Q.push(e.to); inq[e.to] = 1;
    }
    }
    }
    }
    if (d[t] == INF) return false;
    flow += a[t];
    cost += d[t] * a[t];

    for (int u = t; u != s; u = edges[p[u]].from){
    edges[p[u]].flow += a[t];
    edges[p[u] ^ 1].flow -= a[t];
    }
    return true;
    }

    int MinCostMaxFlow(int s, int t, int & cost){
    int flow = 0; cost = 0;
    while (BellmanFord(s, t, flow, cost));
    return flow;
    }
    };

    /*
    S:0 Wi:[1,n] Ui:[n+1,2n] k:[2n+1] T[2n+2]
    */

    int main(){
    MCMF D;
    int n, m;
    scanf("%d %d", &n, &m);
    int s = 0, t = 2 * n + 2, k = 2 * n + 1;
    int tmp;
    D.init(2 * n + 3);
    D.AddEdge(s, k, m, 0);
    for (int i = 1; i <= n; i += 1){
    scanf("%d", &tmp);
    D.AddEdge(s, i, tmp, 0);
    D.AddEdge(i + n, t, tmp, 0);
    D.AddEdge(k, i + n, INF, 0);
    }
    for (int i = 1; i < n; i += 1){
    for (int j = i + 1; j <= n; j += 1){
    scanf("%d", &tmp);
    if (tmp != -1) D.AddEdge(i, j + n, INF, tmp);
    }
    }

    int ans; D.MinCostMaxFlow(s, t, ans);

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

    //Sy;
    return 0;
    }
    ```

  • 0
    @ 2014-05-19 21:27:46

    按某云神的方法建图就可以了Orz,第一次用zkw,好快……
    http://hi.baidu.com/macaulish64/item/7137993446fc99e9382ffa73
    测试数据 #0: Accepted, time = 62 ms, mem = 3456 KiB, score = 10
    测试数据 #1: Accepted, time = 78 ms, mem = 3452 KiB, score = 10
    测试数据 #2: Accepted, time = 7 ms, mem = 3456 KiB, score = 10
    测试数据 #3: Accepted, time = 62 ms, mem = 3456 KiB, score = 10
    测试数据 #4: Accepted, time = 15 ms, mem = 3456 KiB, score = 10
    测试数据 #5: Accepted, time = 62 ms, mem = 3452 KiB, score = 10
    测试数据 #6: Accepted, time = 78 ms, mem = 3456 KiB, score = 10
    测试数据 #7: Accepted, time = 109 ms, mem = 3456 KiB, score = 10
    测试数据 #8: Accepted, time = 109 ms, mem = 3456 KiB, score = 10
    测试数据 #9: Accepted, time = 93 ms, mem = 3452 KiB, score = 10

  • 0
    @ 2013-09-02 19:36:29

    学习了。,。

  • 0
    @ 2010-04-06 20:46:35

    Accepted 有效得分:100 有效耗时:529ms

    有点慢

    那个点内的反向弧是费用20000(不是-20000),弄错了......

  • 0
    @ 2010-03-14 22:00:38

    很经典的模型 ~

  • 0
    @ 2009-09-26 12:13:12

    杯具,为了个SX错误WA了2次。

  • 0
    @ 2009-07-23 08:49:16

    编译通过...

    ├ 测试数据 01:答案正确... 0ms

    ├ 测试数据 02:答案正确... 0ms

    ├ 测试数据 03:答案正确... 0ms

    ├ 测试数据 04:答案正确... 0ms

    ├ 测试数据 05:答案正确... 0ms

    ├ 测试数据 06:答案正确... 0ms

    ├ 测试数据 07:答案正确... 0ms

    ├ 测试数据 08:答案正确... 41ms

    ├ 测试数据 09:答案正确... 103ms

    ├ 测试数据 10:答案正确... 134ms

    ---|---|---|---|---|---|---|---|-

    Accepted 有效得分:100 有效耗时:278ms

    第一次。。。输出了调试的东东

    膜拜CJF神牛。

  • 0
    @ 2009-07-22 18:16:08

    ..顽强的用了 AC 。。

  • 0
    @ 2009-07-21 19:53:11

    SPFA用SLF就能0ms了!(注意要写

  • 0
    @ 2009-06-29 02:01:33

    编译通过...

    ├ 测试数据 01:答案正确... 0ms

    ├ 测试数据 02:答案正确... 0ms

    ├ 测试数据 03:答案正确... 0ms

    ├ 测试数据 04:答案正确... 0ms

    ├ 测试数据 05:答案正确... 0ms

    ├ 测试数据 06:答案正确... 0ms

    ├ 测试数据 07:答案正确... 0ms

    ├ 测试数据 08:答案正确... 0ms

    ├ 测试数据 09:答案正确... 0ms

    ├ 测试数据 10:答案正确... 0ms

    ---|---|---|---|---|---|---|---|-

    Accepted 有效得分:100 有效耗时:0ms

    SLF 王道 !!!

    膜拜 CJF 天牛 !!!

    最开始跑出来的一直是零,后来发现在添加两个国家之间的那个弧我把费用打成了零。。。最近没状态。。。

  • 0
    @ 2009-06-20 08:15:18

    感谢陈健飞神牛的题解!

    将点的费用设为一个很小的数,这方法太神了!

    第100人AC,庆祝一下!

  • 0
    @ 2009-06-11 21:59:36

    zkw费用流就是快……

    0msAC了!

  • 0
    @ 2009-04-13 16:22:01

    ├ 测试数据 01:答案正确... 0ms

    ├ 测试数据 02:答案正确... 0ms

    ├ 测试数据 03:答案正确... 0ms

    ├ 测试数据 04:答案正确... 0ms

    ├ 测试数据 05:答案正确... 0ms

    ├ 测试数据 06:答案正确... 0ms

    ├ 测试数据 07:答案正确... 0ms

    ├ 测试数据 08:答案正确... 72ms

    ├ 测试数据 09:答案正确... 134ms

    ├ 测试数据 10:答案正确... 134ms

  • 0
    @ 2009-04-03 20:57:52

    编译通过...

    ├ 测试数据 01:答案正确... 0ms

    ├ 测试数据 02:答案正确... 0ms

    ├ 测试数据 03:答案正确... 0ms

    ├ 测试数据 04:答案正确... 0ms

    ├ 测试数据 05:答案正确... 0ms

    ├ 测试数据 06:答案正确... 0ms

    ├ 测试数据 07:答案正确... 0ms

    ├ 测试数据 08:答案正确... 166ms

    ├ 测试数据 09:答案正确... 275ms

    ├ 测试数据 10:答案正确... 338ms

    ---|---|---|---|---|---|---|---|-

    Accepted 有效得分:100 有效耗时:779ms

    我太菜了,现在才会费用流,不过A了就好

  • 0
    @ 2009-03-26 19:06:21

    没加优化前

    Accepted 有效得分:100 有效耗时:776ms

    加了一个小优化后

    Accepted 有效得分:100 有效耗时:0ms

    强烈在spfa时队首队尾两端插入,效率明摆着

    而且只不过加了一行

  • 0
    @ 2009-03-12 20:54:05

    注意。。每个节点访问的次数是固定的。且一定有M个人出去访问

  • 0
    @ 2009-02-17 21:58:46

    太好了!!!

    一遍编完没有调试就过了!!!

  • 0
    @ 2009-01-07 14:46:49

    乱写过完

信息

ID
1213
难度
5
分类
图结构 | 网络流 点击显示
标签
递交数
623
已通过
202
通过率
32%
被复制
2
上传者