题解

6 条题解

  • 2
    @ 2018-03-29 13:22:20

    建图方式参见 SCOI 2007 修车,但这道题数据范围更大,需要动态加边:

    • 由于我们跑一次最短路只能找出一次增广路,所以可以暂时不连不需要的边。
    • 首先把所有厨师做倒数第 \(1\) 道菜与所有菜连边,那么找到的增广路上一定经过了一个点,设它表示第 \(i\) 个厨师做倒数第 \(1\) 道菜。
    • 然后添加第 \(i\) 个厨师做倒数第 \(2\) 道菜的点,与汇点和所有菜连边,以此类推。
    • 因为倒数第 \(k\) 道菜的代价一定比倒数 \(k+1\) 道菜贵,所以如果流没流向倒数第 \(k\) 道菜是不可能流向倒数第 \(k+1\) 道菜的。
    #include <bits/stdc++.h>
    using namespace std;
    
    const int maxn = 81000;
    int n, m, sum, cnt, ans, p[45], a[45][105];
    int head[maxn], dist[maxn], incf[maxn], pre[maxn];
    bool inq[maxn];
    struct edge {
        int to, cap, cost, nxt;
    } e[100010];
    
    void add_edge(int from, int to, int cap, int cost) {
        e[cnt] = (edge){to, cap, cost, head[from]}, head[from] = cnt++;
        e[cnt] = (edge){from, 0, -cost, head[to]}, head[to] = cnt++;
    }
    
    bool spfa(int s, int t) {
        fill(dist, dist + maxn, INT_MAX);
        memset(inq, 0, sizeof(inq));
        queue<int> q;
        q.push(s);
        dist[s] = 0;
        inq[s] = 1;
        incf[s] = INT_MAX;
        while (!q.empty()) {
            int v = q.front();
            inq[v] = 0;
            q.pop();
            for (int i = head[v]; i != -1; i = e[i].nxt) {
                if (e[i].cap > 0 && dist[e[i].to] > dist[v] + e[i].cost) {
                    dist[e[i].to] = dist[v] + e[i].cost;
                    incf[e[i].to] = min(incf[v], e[i].cap);
                    pre[e[i].to] = i;
                    if (!inq[e[i].to]) {
                        q.push(e[i].to);
                        inq[e[i].to] = 1;
                    }
                }
            }
        }
        return dist[t] != INT_MAX;
    }
    
    void update(int s, int t) {
        int x = t;
        while (x != s) {
            int i = pre[x];
            e[i].cap -= incf[t];
            e[i ^ 1].cap += incf[t];
            x = e[i ^ 1].to;
        }
        ans += dist[t] * incf[t];
    }
    
    void edmonds_karp(int s, int t) {
        while (spfa(s, t)) {
            update(s, t);
            int x = e[pre[t] ^ 1].to;
            add_edge(x + 1, t, 1, 0);
            for (int i = 1; i <= n; i++) {
                add_edge(i + sum * m, x + 1, 1, a[i][x / sum + 1] * (x % sum + 1));
            }
        }
    }
    
    int main() {
        memset(head, -1, sizeof(head));
        scanf("%d %d", &n, &m);
        for (int i = 1; i <= n; i++) {
            scanf("%d", &p[i]);
            sum += p[i];
        }
        const int s = 0, t = n + sum * m + 1;
        for (int i = 1; i <= n; i++) {
            add_edge(s, i + sum * m, p[i], 0);
            for (int j = 1; j <= m; j++) {
                scanf("%d", &a[i][j]);
                add_edge(i + sum * m, (j - 1) * sum + 1, 1, a[i][j]);
            }
        }
        for (int i = 1; i <= m; i++) {
            add_edge((i - 1) * sum + 1, t, 1, 0);
        }
        edmonds_karp(s, t);
        printf("%d\n", ans);
        return 0;
    }
    
  • 0
    @ 2015-03-23 18:31:00

    #include<iostream>
    #include<cstdio>
    #include<cstring>
    #include<queue>
    #include<vector>
    using namespace std;
    const int maxn=520130;
    const int INF=987654321;
    struct Edge{
    int from,to,cap,flow,cost;
    };
    int P[maxn],Time[45][110],tot=0,cnt[110];
    vector<Edge>edges;
    vector<int>G[maxn];
    int n,m,s,t;
    int dist[maxn],a[maxn],p[maxn];
    bool inQ[maxn];
    void Addedge(int from,int to,int cap,int cost){
    Edge e;
    e.from=from,e.to=to,e.cap=cap,e.flow=0,e.cost=cost;
    edges.push_back(e);
    e.from=to,e.to=from,e.cap=0,e.flow=0,e.cost=-cost;
    edges.push_back(e);
    int M=edges.size();
    G[from].push_back(M-2);
    G[to].push_back(M-1);
    }
    bool spfa(int &New,int &Maxflow,int &Mincost){
    for(int i=s;i<=t;i++)dist[i]=INF;
    memset(inQ,0,sizeof(inQ));
    dist[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++)
    { Edge& e=edges[G[u][i]];
    if(e.cap>e.flow &&dist[e.to]>dist[u]+e.cost)
    { dist[e.to]=dist[u]+e.cost;
    p[e.to]=G[u][i];
    a[e.to]=min(a[u],e.cap-e.flow);
    if(!inQ[e.to]){inQ[e.to]=1;Q.push(e.to);}
    }
    }
    }
    if(dist[t]==INF)return false;
    Maxflow+=a[t];
    Mincost+=dist[t]*a[t];
    int u=t;
    New=(edges[p[u]].from-n)/tot+1;
    //cout<<"New: "<<New<<endl;
    cnt[New]++;
    while(u!=s)
    { edges[p[u]].flow+=a[t];
    edges[p[u]^1].flow-=a[t];
    u=edges[p[u]].from;
    }
    return true;
    }
    int mincost(){
    int Maxflow=0,Mincost=0,New;
    while(spfa(New,Maxflow,Mincost))
    { for(int i=1;i<=n;i++)
    Addedge(i,n+(New-1)*tot+cnt[New],1,Time[i][New]*cnt[New]);
    Addedge(n+(New-1)*tot+cnt[New],t,1,0);
    }
    return Mincost;
    }
    void read_data(){
    scanf("%d%d",&n,&m);

    for(int i=1;i<=n;i++)
    { scanf("%d",&P[i]);
    tot+=P[i];
    }
    for(int i=1;i<=n;i++)
    for(int j=1;j<=m;j++)
    scanf("%d",&Time[i][j]);

    }
    void Build_graph(){
    s=0;t=n+m*tot+1;
    //cout<<"tot: "<<tot<<endl;
    for(int i=1;i<=n;i++)
    Addedge(s,i,P[i],0);
    for(int j=1;j<=m;j++)
    {Addedge(n+tot*(j-1)+1,t,1,0);
    cnt[j]=1;
    }
    for(int i=1;i<=n;i++)
    for(int j=1;j<=m;j++)
    Addedge(i,n+(j-1)*tot+cnt[j],1,Time[i][j]*cnt[j]);
    }
    int main(){
    read_data();
    Build_graph();
    printf("%d\n",mincost());
    return 0;
    }

  • 0
    @ 2013-12-14 22:35:00

    加了LLL之后快了好多。。。
    编译成功

    测试数据 #0: Accepted, time = 0 ms, mem = 7676 KiB, score = 10
    测试数据 #1: Accepted, time = 811 ms, mem = 9208 KiB, score = 10
    测试数据 #2: Accepted, time = 312 ms, mem = 8828 KiB, score = 10
    测试数据 #3: Accepted, time = 15 ms, mem = 7976 KiB, score = 10
    测试数据 #4: Accepted, time = 15 ms, mem = 7744 KiB, score = 10
    测试数据 #5: Accepted, time = 31 ms, mem = 7924 KiB, score = 10
    测试数据 #6: Accepted, time = 156 ms, mem = 8572 KiB, score = 10
    测试数据 #7: Accepted, time = 514 ms, mem = 10284 KiB, score = 10
    测试数据 #8: Accepted, time = 967 ms, mem = 11136 KiB, score = 10
    测试数据 #9: Accepted, time = 702 ms, mem = 11136 KiB, score = 10
    Accepted, time = 3523 ms, mem = 11136 KiB, score = 100

  • 0
    @ 2013-12-14 21:38:19

    终于过了。。。冷死。。。
    我是这么做的,分类讨论一下,边数多的用zkw费用流,边数少的SPFA,记得动态建图。
    编译成功

    测试数据 #0: Accepted, time = 0 ms, mem = 7672 KiB, score = 10
    测试数据 #1: Accepted, time = 1341 ms, mem = 9212 KiB, score = 10
    测试数据 #2: Accepted, time = 452 ms, mem = 8828 KiB, score = 10
    测试数据 #3: Accepted, time = 15 ms, mem = 7972 KiB, score = 10
    测试数据 #4: Accepted, time = 15 ms, mem = 7740 KiB, score = 10
    测试数据 #5: Accepted, time = 31 ms, mem = 7928 KiB, score = 10
    测试数据 #6: Accepted, time = 156 ms, mem = 8568 KiB, score = 10
    测试数据 #7: Accepted, time = 1279 ms, mem = 10284 KiB, score = 10
    测试数据 #8: Accepted, time = 1216 ms, mem = 11140 KiB, score = 10
    测试数据 #9: Accepted, time = 686 ms, mem = 11144 KiB, score = 10
    Accepted, time = 5191 ms, mem = 11144 KiB, score = 100

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

    using namespace std ;

    #define MAXN 50
    #define MAXM 110
    #define MAXP 810
    #define MAXV 100010
    #define clear( x ) memset( x , 0 , sizeof( x ) )
    #define inf 0x7fffffff

    struct edge {
    edge *next , *pair ;
    int t , f , c ;
    edge ( ) {
    next = pair = NULL ;
    }
    } *head[ MAXV ] ;

    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 S , T , V , node[ MAXM ][ MAXP ] , w[ MAXV ][ 2 ] , last[ MAXM ] ;
    bool visit[ MAXM ][ MAXP ] ;

    int Time[ MAXN ][ MAXM ] , n , m , p[ MAXN ] , P = 0 ;

    int cost = 0 , dist[ MAXV ] , slack[ MAXV ] ;
    bool f[ MAXV ] ;

    int aug( int v , int flow ) {
    if ( v == T ) {
    cost += dist[ S ] * flow ; return flow ;
    }
    if ( w[ v ][ 1 ] < P ) if ( ! visit[ w[ v ][ 0 ] ][ w[ v ][ 1 ] + 1 ] ) {
    visit[ w[ v ][ 0 ] ][ w[ v ][ 1 ] + 1 ] = true ;
    node[ w[ v ][ 0 ] ][ w[ v ][ 1 ] + 1 ] = ++ V ;
    w[ V ][ 0 ] = w[ v ][ 0 ] , w[ V ][ 1 ] = w[ v ][ 1 ] + 1 ;
    AddEdge( V , T , 1 , 0 ) ;
    for ( int i = 0 ; i ++ < n ; ) AddEdge( i , V , 1 , Time[ i ][ w[ V ][ 0 ] ] * w[ V ][ 1 ] ) ;
    dist[ V ] = 0 ; f[ V ] = true ; slack[ V ] = inf ;
    }
    f[ v ] = false ; 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 ++ < V ; ) if ( f[ i ] ) delta = min( delta , slack[ i ] ) ;
    if ( delta == inf ) return false ;
    for ( int i = 0 ; i ++ < V ; ) if ( ! f[ i ] ) dist[ i ] += delta ;
    return true ;
    }

    void costflow( ) {
    for ( int i = 0 ; i ++ < V ; ) dist[ i ] = 0 ;
    do {
    for ( int i = 0 ; i ++ < V ; ) slack[ i ] = inf ;
    do {
    for ( int i = 0 ; i ++ < V ; ) f[ i ] = true ;
    } while ( aug( S ,inf ) ) ;
    } while ( relabel( ) ) ;
    }

    int pre[ MAXV ] , Q[ MAXV * 10 ] ;
    edge *Aug[ MAXV ] ;

    void spfa( ) {
    for ( int i = 0 ; i ++ < V ; ) dist[ i ] = inf , f[ i ] = false ;
    int Head = 0 , tail = 0 ;
    dist[ S ] = 0 , Q[ ++ tail ] = S , pre[ S ] = 0 , f[ S ] = true ;
    while ( Head < tail ) {
    int v = Q[ ++ Head ] ;
    f[ v ] = false ;
    for ( edge *p = head[ v ] ; p ; p = p -> next ) if ( p -> f && dist[ p -> t ] > dist[ v ] + p -> c ) {
    dist[ p -> t ] = dist[ v ] + p -> c ;
    if ( ! f[ p -> t ] ) {
    f[ p -> t ] = true ; Q[ ++ tail ] = p -> t ;
    }
    pre[ p -> t ] = v , Aug[ p -> t ] = p ;
    }
    }
    }

    int main( ) {
    scanf( "%d%d" , &n , &m ) ;
    for ( int i = 0 ; i ++ < n ; ) {
    scanf( "%d" , &p[ i ] ) ; P += p[ i ] ;
    }
    clear( head ) ;
    V = n ; S = ++ V , T = ++ V ;
    for ( int i = 0 ; i ++ < n ; ) {
    AddEdge( S , i , p[ i ] , 0 ) ;
    }
    clear( visit ) , clear( w ) ;
    visit[ 0 ][ 1 ] = true ;
    for ( int i = 0 ; i ++ < n ; ) for ( int j = 0 ; j ++ < m ; ) scanf( "%d" , &Time[ i ][ j ] ) ;
    for ( int i = 0 ; i ++ < m ; ) {
    visit[ i ][ 1 ] = true ; node[ i ][ 1 ] = ++ V ; last[ i ] = 1 ;
    w[ V ][ 0 ] = i , w[ V ][ 1 ] = 1 ;
    for ( int j = 0 ; j ++ < n ; ) AddEdge( j , V , 1 , Time[ j ][ i ] ) ;
    AddEdge( V , T , 1 , 0 ) ;
    }
    if ( ( m + P ) * n > 30000 ) costflow( ) ; else {
    for ( int i = 0 ; i ++ < P ; ) {
    spfa( ) ; cost += dist[ T ] ; if ( i == P ) break ;
    for ( int i = T ; pre[ i ] ; i = pre[ i ] ) Aug[ i ] -> f -- , Aug[ i ] -> pair -> f ++ ;
    for ( int j = 0 ; j ++ < m ; ) if ( ! head[ node[ j ][ last[ j ] ] ] -> f ) {
    node[ j ][ ++ last[ j ] ] = ++ V ;
    for ( int k = 0 ; k ++ < n ; ) AddEdge( k , V , 1 , Time[ k ][ j ] * last[ j ] ) ;
    AddEdge( V , T , 1 , 0 ) ;
    }
    }
    }
    printf( "%d\n" , cost ) ;
    return 0 ;
    }

  • 1

信息

ID
1726
难度
6
分类
图结构 | 网络流 点击显示
标签
递交数
422
已通过
104
通过率
25%
被复制
2
上传者