D Kejin Game

Description

  题号：UVA7264   你有一个有向技能图。点表示技能。若\(x\)到\(y\)有一条有向边，则表示\(x\)是\(y\)的前置技能。你可以氪\(c_i\)元以消除这条有向边，即你普通地学\(y\)时可以未学会\(x\)。你学会一个技能有两种方法：1、普通地学完它的所有前置技能，并氪\(a_{x}\)元；2、暴力地直接氪\(b_{x}\)元。问你学会技能\(s'\)时，最少氪金多少元。
  \(1 \leq n \leq 500,1 \leq m \leq 10000,1 \leq x_1,x_2 \leq 1000000\)

Sample Input

2
5 5 5
1 2 5
1 3 5
2 4 8
4 5 10
3 5 15
3 5 7 9 11
100 100 100 200 200
5 5 5
1 2 5
1 3 5
2 4 8
4 5 10
3 5 15
3 5 7 9 11
5 5 5 50 50

Sample Output

31
26

Solution

  考虑到对于一个技能，需要分别算是“学会所有前置技能”还是“学部分氪部分”还是“暴力学”更划算，应用了网络流。
  将一个技能拆分为两个点，标为\(i\)和\(i'\)。从S连边到\(i\)，流量为\(a_i\)；从\(i\)连边到\(i'\)，流量为\(b_i\)；从\(x'\)连边到\(y\)，流量为\(c_i\)；最后从\(s\)连边到T，流量为INF。
  这样，通过在点\(i\)处的流量限制，我们已经可以解决到底怎么选这个问题了。那么跑一下源汇的最小割，就是所要求的最小花\((ke)\)费\((jin)\)了。

#include<bits/stdc++.h>
using namespace std;
const int maxn = 2020;
const int INF = 1e9+7;
typedef long long ll;

struct Edge{
    int from,to,cap;
    Edge(int from,int to,int cap):from(from),to(to),cap(cap){}
};
int n,m,s,t,totflow;
vector<Edge> edges;
vector<int> G[maxn];
bool vis[maxn];
int d[maxn];
int cur[maxn];

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

inline bool BFS()
{
    memset(vis,0,sizeof vis);
    queue<int> Q;
    Q.push(s);
    d[s]=0;
    vis[s]=1;
    while(!Q.empty())
    {
        int x=Q.front();
        Q.pop();
        for(int i=0;i<(int)G[x].size();++i)
        {
            Edge& e=edges[G[x][i]];
            if(!vis[e.to]&&e.cap)
            {
                vis[e.to]=1;
                d[e.to]=d[x]+1;
                Q.push(e.to);
            }
        }
    }
    return vis[t];
}

inline int DFS(int x,int a)
{
    if(x==t||a==0) return a;
    int flow=0,f=0;
    for(int& i=cur[x];i<(int)G[x].size();++i)
    {
        Edge& e=edges[G[x][i]];
        if(d[x]+1==d[e.to]&&(f=DFS(e.to,min(a,e.cap)))>0)
        {
            e.cap-=f;
            edges[G[x][i]^1].cap+=f;
            flow+=f;
            a-=f;
            if(a==0) break;
        }
    }
    return flow;
}

inline int Maxflow(int s,int t)
{
    int flow=0;
    while(BFS())
    {
        memset(cur,0,sizeof(cur));
        flow+=DFS(s,INF);
    }
    return flow;
}

inline int read(){
    int x=0,f=1;
    char ch=getchar();
    while(ch<'0'||ch>'9'){
        ch=getchar();
    }
    while(ch>='0'&&ch<='9'){
        x=(x<<1)+(x<<3)+(ch^48);
        ch=getchar();
    }
    return x*f;
}

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

inline void readin()
{
    int temp,aa,bb,cc,le,ri;
    le=read(),ri=read(),temp=read();
    s=0;
    n=t=2*le+1;
    init();
    for(int i=1;i<=ri;++i)
    {
        aa=read();bb=read();cc=read();
        AddEdge(aa+le,bb,cc);
    }
    for(int i=1;i<=le;++i) aa=read(),AddEdge(0,i,aa);
    for(int i=1;i<=le;++i) aa=read(),AddEdge(i,i+le,aa);
    AddEdge(temp+le,t,INF);
}

int main()
{
    int t;
    t=read();
    for(int i=1;i<=t;++i)
    {
        readin();
        printf("%d\n",Maxflow(s,t));
    }
    return 0;
}