“科林明伦杯”哈尔滨理工大学第十届程序设计竞赛(同步赛)

“科林明伦杯”哈尔滨理工大学第十届程序设计竞赛(同步赛) - G养花

链接：https://ac.nowcoder.com/acm/contest/5758/G
来源：牛客网

题目描述

小明是一个魔法师，他有n棵植物，所有植物排成一排，植物的初始高度为数组h，小明有一些强迫症，他想
让植物的高度都恰好达到k，小明有m瓶药水，但药水分为4种：
1.选择一棵高度为a0的植物变为b0高度的植物
2.选择一棵高度在[a1,a2]区间内的植物变为b1高度的植物
3.选择一棵高度为a1的植物变为[b1, b2]区间内某一高度的植物
4.选择一棵高度在[a1,a2]区间内的植物变为[b1,b2]区间内某一高度的植物
由于每瓶药水有C瓶库存，小明想知道他最多让多少棵植物高度达到k

输入描述:

输入数据第一行是t，表示数据的组数，接下来每组数据输入n，m，k，
接下来一行输入n个数，分别是每棵植物的高度h[i]（1 <= h[i] < k）,
接下来m行开头的两个数字为op和c表示药水是哪一种和该种药水有几瓶，输入如下
若 op=1，则接下来两个整数 a0，b0，意义如上文所述。
若 op=2，则接下来三个整数 a1,a2,b1，意义如上文所述。
若 op=3，则接下来三个整数 a1,b1,b2，意义如上文所述。
若 op=4，则接下来四个整数 a1,a2,b1,b2，意义如上文所述。
数据保证，所有 1 <= a0,b0,a1,b1,a2,b2 <= k
（t <= 10，n <= 1e4，m <= 300，k <= 100，c <=1e6）

输出描述:

输出一个整数，表示最多有多少颗植物能生涨到k。

思路：

算法：流量网络求最大流。

建图方法：

节点 $\mathit i$ 代表高度为 $\mathit i$ 的花

设节点 $S=0$ 为源点， $T=k+1$ 为汇点。

用数组 $cnt_i$ 记录最初有多少个高度为 $\mathit i$ 的花，

源点和每一个高度节点可以建边： $(S,i,cnt_i)$ 代表从 $\mathit S$ 指向 $\mathit i$ 流量为 $cnt_i$ 的单向边。

四种药水也可以根据题意分别建立高度节点和高度节点之间的边。

最后建立高度为 $\mathit k$ 的节点与汇点的边，流量设为无穷大。即： $(k,T,INF)$

然后求 $S->T$ 的最大流即可。

样例1的流量网络为：

代码：

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cmath>
#include <queue>
#include <stack>
#include <map>
#include <set>
#include <vector>
#include <iomanip>
#include <sstream>
#include <bitset>
#include <unordered_map>
// #include <bits/stdc++.h>
#define ALL(x) (x).begin(), (x).end()
#define sz(a) int(a.size())
#define rep(i,x,n) for(int i=x;i<n;i++)
#define repd(i,x,n) for(int i=x;i<=n;i++)
#define pii pair<int,int>
#define pll pair<long long ,long long>
#define gbtb ios::sync_with_stdio(false),cin.tie(0),cout.tie(0)
#define MS0(X) memset((X), 0, sizeof((X)))
#define MSC0(X) memset((X), '\0', sizeof((X)))
#define pb push_back
#define mp make_pair
#define fi first
#define se second
#define eps 1e-6
#define chu(x)  if(DEBUG_Switch) cout<<"["<<#x<<" "<<(x)<<"]"<<endl
#define du3(a,b,c) scanf("%d %d %d",&(a),&(b),&(c))
#define du2(a,b) scanf("%d %d",&(a),&(b))
#define du1(a) scanf("%d",&(a));
using namespace std;
typedef long long ll;
ll gcd(ll a, ll b) {return b ? gcd(b, a % b) : a;}
ll lcm(ll a, ll b) {return a / gcd(a, b) * b;}
ll powmod(ll a, ll b, ll MOD) { if (a == 0ll) {return 0ll;} a %= MOD; ll ans = 1; while (b) {if (b & 1) {ans = ans * a % MOD;} a = a * a % MOD; b >>= 1;} return ans;}
ll poww(ll a, ll b) { if (a == 0ll) {return 0ll;} ll ans = 1; while (b) {if (b & 1) {ans = ans * a ;} a = a * a ; b >>= 1;} return ans;}
void Pv(const vector<int> &V) {int Len = sz(V); for (int i = 0; i < Len; ++i) {printf("%d", V[i] ); if (i != Len - 1) {printf(" ");} else {printf("\n");}}}
void Pvl(const vector<ll> &V) {int Len = sz(V); for (int i = 0; i < Len; ++i) {printf("%lld", V[i] ); if (i != Len - 1) {printf(" ");} else {printf("\n");}}}
inline long long readll() {long long tmp = 0, fh = 1; char c = getchar(); while (c < '0' || c > '9') {if (c == '-') fh = -1; c = getchar();} while (c >= '0' && c <= '9') tmp = tmp * 10 + c - 48, c = getchar(); return tmp * fh;}
inline int readint() {int tmp = 0, fh = 1; char c = getchar(); while (c < '0' || c > '9') {if (c == '-') fh = -1; c = getchar();} while (c >= '0' && c <= '9') tmp = tmp * 10 + c - 48, c = getchar(); return tmp * fh;}
void pvarr_int(int *arr, int n, int strat = 1) {if (strat == 0) {n--;} repd(i, strat, n) {printf("%d%c", arr[i], i == n ? '\n' : ' ');}}
void pvarr_LL(ll *arr, int n, int strat = 1) {if (strat == 0) {n--;} repd(i, strat, n) {printf("%lld%c", arr[i], i == n ? '\n' : ' ');}}
const int maxn = 100010;
const int inf = 0x3f3f3f3f;
/*** TEMPLATE CODE * * STARTS HERE ***/
#define DEBUG_Switch 0
#define N 1500
#define INF 1e13
struct Edge
{
    int from, to;
    ll  cap, flow; // cap 并不减少，只是flow在增，有残余就是cap>flow
};
struct ISAP
{
    int n, m, s, t;
    vector<Edge>edges;
    vector<int>G[N];
    bool vis[N];
    int d[N], cur[N];
    int p[N], num[N]; //比Dinic算法多了这两个数组，p数组标记父亲结点，num数组标记距离d[i]存在几个
    void addedge(int from, int to, ll cap)
    {
        // cout << from << " " << to << " " << cap << endl;
        edges.push_back((Edge) {from, to, cap, 0});
        edges.push_back((Edge) {to, from, 0, 0});
        int m = edges.size();
        G[from].push_back(m - 2);
        G[to].push_back(m - 1);
    }
    void init()
    {
        MS0(d);
        edges.clear();
        for (int i = 0; i <= n; ++i) {
            G[i].clear();
        }
    }
    ll Augumemt()
    {
        ll x = t, a = INF;
        while (x != s) //找最小的残量值
        {
            Edge&e = edges[p[x]];
            a = min(a, e.cap - e.flow);
            x = edges[p[x]].from;
        }
        x = t;
        while (x != s) //增广
        {
            edges[p[x]].flow += a;
            edges[p[x] ^ 1].flow -= a;
            x = edges[p[x]].from;
        }
        return a;
    }
    void bfs()//逆向进行bfs
    {
        memset(vis, 0, sizeof(vis));
        queue<int>q;
        q.push(t);
        d[t] = 0;
        vis[t] = 1;
        while (!q.empty())
        {
            int x = q.front(); q.pop();
            int len = G[x].size();
            for (int i = 0; i < len; i++)
            {
                Edge&e = edges[G[x][i]];
                if (!vis[e.from] && e.cap > e.flow)
                {
                    vis[e.from] = 1;
                    d[e.from] = d[x] + 1;
                    q.push(e.from);
                }
            }
        }
    }

    ll Maxflow(int s, int t) //根据情况前进或者后退，走到汇点时增广
    {
        this->s = s;
        this->t = t;
        ll flow = 0;
        bfs();
        memset(num, 0, sizeof(num));
        for (int i = 0; i < n; i++)
            num[d[i]]++;
        int x = s;
        memset(cur, 0, sizeof(cur));
        while (d[s] < n)
        {
            if (x == t) //走到了汇点，进行增广
            {
                flow += Augumemt();
                x = s; //增广后回到源点
            }
            int ok = 0;
            for (int i = cur[x]; i < G[x].size(); i++)
            {
                Edge&e = edges[G[x][i]];
                if (e.cap > e.flow && d[x] == d[e.to] + 1)
                {
                    ok = 1;
                    p[e.to] = G[x][i]; //记录来的时候走的边，即父边
                    cur[x] = i;
                    x = e.to; //前进
                    break;
                }
            }
            if (!ok) //走不动了，撤退
            {
                int m = n - 1; //如果没有弧，那么m+1就是n，即d[i]=n
                for (int i = 0; i < G[x].size(); i++)
                {
                    Edge&e = edges[G[x][i]];
                    if (e.cap > e.flow)
                        m = min(m, d[e.to]);
                }
                if (--num[d[x]] == 0)break; //如果走不动了，且这个距离值原来只有一个，那么s-t不连通，这就是所谓的“gap优化”
                num[d[x] = m + 1]++;
                cur[x] = 0;
                if (x != s)
                    x = edges[p[x]].from; //退一步，沿着父边返回
            }
        }
        return flow;
    }
    //  调用前给这里的n赋值，一般为n=T+1;
} gao;


int n;
int m, k;
int cnt[maxn];

// bool check(ll mid)
// {
//     gao.init();
//     int S = 0;
//     int T = n + 10;
//     gao.n = T + 1;
//     gao.addedge(n + i, T, d[i]);
//     ll res = gao.Maxflow(S, T);
// }
int main()
{
#if DEBUG_Switch
    freopen("C:\\code\\input.txt", "r", stdin);
#endif
    //freopen("C:\\code\\output.txt","r",stdin);
    int t;
    t = readint();
    while (t--)
    {
        n = readint();
        m = readint();
        k = readint();
        repd(i, 1, k)
        {
            cnt[i] = 0;
        }
        repd(i, 1, n)
        {
            int x = readint();
            cnt[x]++;
        }
        int S = 0;
        repd(i, 1, k)
        {
            gao.addedge(S, i , cnt[i] );
        }
        int id = k;
        repd(i, 1, m)
        {
            int op = readint();
            int c = readint();
            if (op == 1)
            {
                int a0 = readint();
                int b0 = readint();
                gao.addedge( a0 , b0, c );
            } else if (op == 2)
            {
                int a1 = readint();
                int a2 = readint();
                int b1 = readint();
                repd(a0, a1, a2)
                {
                    gao.addedge( a0, b1, c );
                }
            } else if (op == 3)
            {
                int a0 = readint();
                int b1 = readint();
                int b2 = readint();
                repd(b0, b1, b2)
                {
                    gao.addedge( a0, b0, c );
                }
            } else if (op == 4)
            {
                int a1 = readint();
                int a2 = readint();
                int b1 = readint();
                int b2 = readint();
                repd(a0, a1, a2)
                {
                    repd(b0, b1, b2)
                    {
                        gao.addedge( a0, b0, c );
                    }
                }
            }
        }
        id++;
        int T = id ;
        gao.addedge(k , T, INF );
        gao.n = T + 1;
        ll res = gao.Maxflow(S, T);
        gao.init();
        printf("%lld\n", res );
    }

    return 0;
}