MYF

UVaLive 7264 Kejin Game

Posted on | In | | Visitors

题目链接

UVaLive 7264 vjudge今天比赛完也挂了，链接自行找吧。。。

方法：网络流

题目分析

题目大意

一个有向图，表示一个技能表，有先后顺序，比如要获得A技能要先获得B技能以及C技能。但是这个游戏可以“克金”，可以花钱直接获得该技能，也可以花钱取消技能依赖，正常修炼也需要花费一些金钱。现在告诉你n, m, s表示技能总数，技能依赖数量，以及最终想要获得的技能数量，问想要学会技能s最少需要花多少钱？

解析

比赛的时候就在犹豫，这题是DP还是网络流，但是DP的状态没法转移。网络流又不知道怎么建图才能把路径上的所有边加起来，做了这题也算有所长进。

建图方式Hihocoder 1252 Kejin Game （最小割）说的很详细了，不再赘述。

这里比较想说一下，为什么要这样建图呢？

其实认真想一下，如果想要学会一个技能，一定选取min(克金, 完成预备技能 + 正常修炼的花费)。如何做出两者的比较呢？后者可以看作是从两个方向流过来的网络流的和，用克金的路径去约束，这样流过克金的路径的流量一定是克金和从两个方向流过来的流量之和的较小结果，我们跑出来的这样的最大流就形成了全图的最小割，完美的解决了这个问题。

网络流方面太弱，要好好看看网络流的材料了。[网络流建模汇总][Edelweiss]

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
#include <set>
#include <map>
#include <stack>
#include <cmath>
#include <queue>
#include <cstdio>
#include <string>
#include <vector>
#include <iomanip>
#include <bitset>
#include <cstring>
#include <iostream>
#include <iosfwd>
#include <deque>
#include <algorithm>
#define Memset(a,val) memset(a,val,sizeof(a))
#define PI acos(-1.0)
#define PB push_back
#define MP make_pair
#define rt(n)       (i == n ? '\n' : ' ')
#define hi         printf("Hi----------\n")
#define IN freopen("input.txt","r",stdin);
#define OUT freopen("output.txt","w",stdout);
#define debug(x) cout<<"Debug : ---"<<x<<"---"<<endl;
#define debug2(x,y) cout<<"Debug : ---"<<x<<" , "<<y<<"---"<<endl;
#pragma comment(linker, "/STACK:1024000000,1024000000")
using namespace std;
typedef pair<int,int> PII;
typedef long long ll;
const int mod=1000000007;
const int INF=0x3f3f3f3f;
const double eps=1e-8;
const int maxn=1e6+10;
namespace ISAP{
    const int Vmax = 420900;
    const int Emax = 420900;
    int n;
    struct Node {
        int v;    // vertex
        int cap;    // capacity
        int flow;   // current flow in this arc
        int nxt;
    } e[Emax * 2];
    int g[Vmax], fcnt;
    int st, ed;
    int dist[Vmax], numbs[Vmax], q[Vmax];
    void adde(int u, int v, int c) {    //单向加边的过程
        e[++fcnt].v = v;
        e[fcnt].cap = c;
        e[fcnt].flow = 0;
        e[fcnt].nxt = g[u];
        g[u] = fcnt;
        e[++fcnt].v = u;
        e[fcnt].cap = 0;
        e[fcnt].flow = 0;
        e[fcnt].nxt = g[v];
        g[v] = fcnt;
    }
    void init(int src,int sink,int n_) {
        memset(g, 0, sizeof(g));
        fcnt = 1;
        n=n_;
        st = src, ed = sink;/*修改*/
    }
    void rev_bfs() {
        int font = 0, rear = 1;
        for (int i = 0; i <= n; i++) { //n为总点数
            dist[i] = Vmax;
            numbs[i] = 0;
        }
        q[font] = ed;
        dist[ed] = 0;
        numbs[0] = 1;
        while(font != rear) {
            int u = q[font++];
            for (int i = g[u]; i; i = e[i].nxt) {
                if (e[i ^ 1].cap == 0 || dist[e[i].v] < Vmax) continue;
                dist[e[i].v] = dist[u] + 1;
                ++numbs[dist[e[i].v]];
                q[rear++] = e[i].v;
            }
        }
    }
    int maxflow() {
        rev_bfs();
        int u, totalflow = 0;
        int curg[Vmax], revpath[Vmax];
        for(int i = 0; i <= n; ++i) curg[i] = g[i];
        u = st;
        while(dist[st] < n) {
            if(u == ed) {   // find an augmenting path
                int augflow = INF;
                for(int i = st; i != ed; i = e[curg[i]].v)
                    augflow = min(augflow, e[curg[i]].cap);
                for(int i = st; i != ed; i = e[curg[i]].v) {
                    e[curg[i]].cap -= augflow;
                    e[curg[i] ^ 1].cap += augflow;
                    e[curg[i]].flow += augflow;
                    e[curg[i] ^ 1].flow -= augflow;
                }
                totalflow += augflow;
                u = st;
            }
            int i;
            for(i = curg[u]; i; i = e[i].nxt)
                if(e[i].cap > 0 && dist[u] == dist[e[i].v] + 1) break;
            if(i) {   // find an admissible arc, then Advance
                curg[u] = i;
                revpath[e[i].v] = i ^ 1;
                u = e[i].v;
            } else {    // no admissible arc, then relabel this vertex
                if(0 == (--numbs[dist[u]])) break;    // GAP cut, Important!
                curg[u] = g[u];
                int mindist = n;
                for(int j = g[u]; j; j = e[j].nxt)
                    if(e[j].cap > 0) mindist = min(mindist, dist[e[j].v]);
                dist[u] = mindist + 1;
                ++numbs[dist[u]];
                if(u != st)
                    u = e[revpath[u]].v;    // Backtrack
            }
        }
        return totalflow;
    }
}
int main(){
    int T,N,m,s,u,v,w;
    scanf("%d",&T);
    while (T--) {
        scanf("%d%d%d",&N,&m,&s);
        ISAP::init(0, 2*N+1, 2*N+2);
        for (int i=0; i<m; i++) {
            scanf("%d%d%d",&u,&v,&w);
            ISAP::adde(u+N, v, w);
        }
        for (int i=1; i<=N; i++) {
            scanf("%d",&w);
            ISAP::adde(0, i, w);
        }
        for (int i=1; i<=N; i++) {
            scanf("%d",&w);
            ISAP::adde(i, i+N, w);
        }
        
        ISAP::adde(s+N, 2*N+1, INF);
        cout<<ISAP::maxflow()<<"\n";
    }
}