“科林明伦杯”哈尔滨理工大学第十届程序设计竞赛(同步赛) - 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;
}
京公网安备 11010502036488号