P2764 最小路径覆盖问题
建模方式
拆所有点为入点和出点两部分，创建超级源点和超级汇点。
连边：源点到所有入点边权值为1表示，每个点只进入一个流量，出点到汇点边权值也为1，表示出度也为1。
然后对图求最大流。
最小路径覆盖=总点数-最大流
代码实现
ll n, m;
struct edge {
ll next;
ll to;
ll val;
}e[210000];
ll head[210000];
ll cnt = 0;
void init() {
cnt = 0;
for (int i = 1; i <= n; i++) {
head[i] = head[i + n] = -1;
}
head[2 * n + 1] = head[0] = -1;
}
void add(ll x, ll y, ll val) {
e[cnt].next = head[x];
e[cnt].to = y;
e[cnt].val = val;
head[x] = cnt++;
}
ll dep[210000];
bool makelevel(ll be,ll en) {
memset(dep, 0, sizeof dep);
queue<ll>q;
q.push(be); dep[be] = 1;
while (q.size()) {
ll x = q.front(); q.pop();
if (x == en)return true;
for (int i = head[x]; i!=-1; i = e[i].next) {
ll y = e[i].to;
if (dep[y] == 0 && e[i].val != 0) {
q.push(y);
dep[y] = dep[x] + 1;
}
}
}
return false;
}
ll dinic(ll x, ll flow, ll en) {
if (x == en)return flow;
ll sum = 0;
for (int i = head[x]; i != -1; i = e[i].next) {
ll y = e[i].to;
if (e[i].val != 0 && dep[y] == dep[x] + 1) {
ll tmp = dinic(y, min(e[i].val, flow - sum), en);
e[i].val -= tmp;
e[i ^ 1].val += tmp;
sum += tmp;
if (sum == flow)return sum;
}
}
return sum;
}
vector<ll>st;
ll v[210000];
void go(ll i, queue<ll>& p) {
p.push(i);
for (int j = head[i]; j != -1; j = e[j].next) {
ll y = e[j].to;
if (y > n && v[y - n] == false && e[j].val == 0) {
v[y - n] = true;
go(y - n, p);
}
}
}
void solve() {
cin >> n >> m;
init();
for (int i = 1; i <= m; i++) {
ll x, y; cin >> x >> y;
add(x, y + n, 1);
add(y + n, x, 0);//反向边
}
ll be = 0;
ll en = 2 * n + 1;
for (int i = 1; i <= n; i++) {
add(be, i, 1);
add(i, be, 0);
add(i + n, en, 1);
add(en, i + n, 0);
}
ll ans = 0;
while (makelevel(be,en)) {
ans += dinic(be, LLONG_MAX, en);
}
v[0] = true;
for (int i = 1; i <= n; i++) {
for (int j = head[i+n]; j != -1; j = e[j].next) {
if (e[j].val == 1&&e[j].to==2*n+1) {
st.push_back(i);
v[i] = true;
}
}
}
queue<ll>p;
for (int i = 0; i < st.size(); i++) {
go(st[i], p);
while (p.size())cout << p.front() << " ", p.pop();
cout << "\n";
}
cout << n - ans << "\n";
}P2765 魔术球问题
建模方式
对于图中条件，对于给定的n，计算在n根柱子上最多可以放多少个球。可以转化为问题，对于给定的n，计算不超过n条路经最多可以覆盖多少满足条件的结点。
最小路径覆盖=总点数-最大流；所以我们可以在每次加一个球之后建模，使用dinic算法求最大流，然后求出在需要n+1根柱子时候的球的数量，减一即是答案。
对于求路径，我们可以再对最终的图跑一次网络流，看哪个点满流他的下一步就是那个点。
代码实现
ll n;
struct edge {
ll next;
ll to;
ll val;
}e[10000000];
ll head[5000];
ll cnt = 0;
void add(ll x, ll y, ll val) {
e[cnt].next = head[x];
e[cnt].to = y;
e[cnt].val = val;
head[x] = cnt++;
}
ll dep[5000];
bool makelevel(ll be, ll en) {
memset(dep, 0, sizeof dep);
queue<ll>q;
q.push(be); dep[be] = 1;
while (q.size()) {
ll x = q.front(); q.pop();
if (x == en)return true;
for (int i = head[x]; i != -1; i = e[i].next) {
ll y = e[i].to;
if (dep[y] == 0 && e[i].val != 0) {
q.push(y);
dep[y] = dep[x] + 1;
}
}
}
return false;
}
ll dinic(ll x, ll flow, ll en) {
if (x == en)return flow;
ll sum = 0;
for (int i = head[x]; i != -1; i = e[i].next) {
ll y = e[i].to;
if (e[i].val != 0 && dep[y] == dep[x] + 1) {
ll tmp = dinic(y, min(e[i].val, flow - sum), en);
e[i].val -= tmp;
e[i ^ 1].val += tmp;
sum += tmp;
if (sum == flow)return sum;
}
}
return sum;
}
ll nex[5000];
bool v[5000];
void solve() {
cin >> n;
memset(head, -1, sizeof head);
ll x = 2000;
ll be = 0;
ll en = x * 2 + 1;
map<ll, ll>p;
for (int i = 1; i <= 100; i++)p[i * i] = 1;
ll num = 0;
deque<ll>q;
while (q.size()<=n) {
num++;
for (int i = 1; i < num; i++) {
if (p[i + num]) {
add(i, num+x, 1);
add(num+x, i, 0);
}
}
add(be, num, 1);
add(num, be, 0);
add(num+x, en, 1);
add(en, num+x, 0);
ll ans = 0;
while (makelevel(be, en)) {
ans += dinic(be, LLONG_MAX, en);
}
if (ans == 0)q.push_back(num);
}
cout << num - 1 << "\n";
memset(head, -1, sizeof head); cnt = 0;
for (int i = 1; i <= num-1; i++)add(be, i, 1), add(i, be, 0), add(i + x, en, 1), add(en,i+x , 0);
for (int i = 1; i <= num-1; i++) {
for (int j = i + 1; j <= num-1; j++) {
if (p[i + j]) {
add(i, j + x, 1);
add(j + x, i, 0);
}
}
}
ll ans = 0;
while (makelevel(be,en)) {
ans += dinic(be, LLONG_MAX, en);
}
memset(nex, -1, sizeof nex);
for (int i = 0; i < cnt; i += 2) {
ll u = e[i ^ 1].to;
ll v = e[i].to - x;
if (u >= 1 && u <= num-1 && e[i].val == 0 && v >= 1 && v <= num-1) nex[u] = v;
}
memset(v, false, sizeof v);
for (int i = 1; i <= num-1; i++) {
if (v[i] == false) {
ll k = i;
while (k != -1) {
cout << k << " ";
v[k] = true;
k = nex[k];
}
cout << "\n";
}
}
}P2766 最长不下降子序列问题
建模方式
问题1：求序列LIS的长度s；
解法：DP求解即可。
问题2：求序列长度为s的不下降子序列最多个数，每次个数只能用一次；
解法：我们按照问题1的DP数组建图，我们将每个点拆为入点和出点，并将其连接，以此保证每个点只用一次。我们将dp数组中的，dp值为1的点与终极源点连接，以此代表可以进入的位置；我们将dp值为s的点与终极汇点连接，以此表示可以退出的点。然后开始枚举所有dp数组中dp[i]=dp[j]+1的点，连接。然后求最大流，即是序列个数。
问题3：若第一个点和第n个点可以无限使用，问最多个数；
解法：我们把第一个点与终极源点的建立一条流量无线的边，然后最后一点与汇点建立一条无限的边。第一个点和第n个点自己的入点和出点的容量也改为无限。然后再重新跑一次最大流。（因为在第二问结束之后，部分政变全已经变为0对于后续无影响，所以不需要重新建图，接着跑即可）
代码实现
ll n;
struct edge {
ll to, next, val;
}e[210000]; ll cnt = 0;
ll head[210000];
void add(ll x, ll y, ll val) {
e[cnt].next = head[x];
e[cnt].to = y;
e[cnt].val = val;
head[x] = cnt++;
}
ll dep[210000];
bool makelevel(ll be, ll en) {
memset(dep, 0, sizeof dep);
queue<ll>q;
q.push(be); dep[be] = 1;
while (q.size()) {
ll x = q.front(); q.pop();
if (x == en)return true;
for (int i = head[x]; i != -1; i = e[i].next) {
ll y = e[i].to;
if (dep[y] == 0 && e[i].val != 0) {
q.push(y);
dep[y] = dep[x] + 1;
}
}
}
return false;
}
ll dinic(ll x, ll flow, ll en) {
if (x == en)return flow;
ll sum = 0;
for (int i = head[x]; i != -1; i = e[i].next) {
ll y = e[i].to;
if (e[i].val != 0 && dep[y] == dep[x] + 1) {
ll tmp = dinic(y, min(e[i].val, flow - sum), en);
e[i].val -= tmp;
e[i ^ 1].val += tmp;
sum += tmp;
if (sum == flow)return sum;
}
}
return sum;
}
void solve() {
cin >> n;
vector<ll>o(n);
for (int i = 0; i < n; i++) {
cin >> o[i];
}
if (n == 1) {
cout << "1\n1\n1\n"; return;
}
vector<ll>dp(n);
ll ans = 0;
for (int i = 0; i < n; i++) {
dp[i] = 1;
for (int j = 0; j < i; j++) {
if (o[i] >= o[j]) {
dp[i] = max(dp[i], dp[j] + 1);
}
}
ans = max(ans, dp[i]);
}
cout << ans << "\n";
memset(head, -1, sizeof head);
ll be = 0;
ll en = n * 2 + 1;
for (int i = 0; i < n; i++) {
add(i + 1, i + 1 + n, 1);
add(i + 1 + n, i + 1, 0);
if (dp[i] == 1) {
add(be, i + 1, 1);
add(i + 1, be, 0);
}
if (dp[i] == ans) {
add(i + 1 + n, en, 1);
add(en, i + 1 + n, 0);
}
for (int j = 0; j < i; j++) {
if (o[j] <= o[i] && dp[j] == dp[i] - 1) {
add(j + n + 1, i + 1, 1);
add(i + 1, j + n + 1, 0);
}
}
}
ll ans2 = 0;
while (makelevel(be,en)) {
ans2 += dinic(be, LLONG_MAX, en);
}
cout << ans2 << "\n";
add(1, 1 + n, LLONG_MAX);
add(1 + n, 1, 0);
add(be, 1, LLONG_MAX);
add(1, be, 0);
add(n, n + n, LLONG_MAX);
add(n + n, n, 0);
if (dp[n - 1] == ans) {
add(n + n, en, LLONG_MAX);
add(en, n + n, 0);
}
while (makelevel(be,en)) {
ans2 += dinic(be, LLONG_MAX, en);
}
cout << ans2 << "\n";
}P2756 飞行员配对方案问题
建模方式
标准二分图最大匹配问题。
我们建图之后，求最大流，既是二分图最大匹配。
代码实现
ll n, m;
struct edge{
ll next, to, val;
}e[210000];
ll head[210000];
ll cnt = 0;
void init() {
cnt = 0;
for (int i = 1; i <= n; i++) {
head[i] = -1;
}
head[n + 1] = head[0] = -1;
}
void add(ll x, ll y, ll val) {
e[cnt].next = head[x];
e[cnt].to = y;
e[cnt].val = val;
head[x] = cnt++;
}
void addxy(ll x, ll y, ll val) {
add(x, y, val);
add(y, x, 0);
}
ll dep[210000];
bool makelevel(ll be, ll en) {
memset(dep, 0, sizeof dep);
queue<ll>q;
q.push(be); dep[be] = 1;
while (q.size()) {
ll x = q.front(); q.pop();
if (x == en)return true;
for (int i = head[x]; i != -1; i = e[i].next) {
ll y = e[i].to;
if (dep[y] == 0 && e[i].val != 0) {
q.push(y);
dep[y] = dep[x] + 1;
}
}
}
return false;
}
ll dinic(ll x, ll flow, ll en) {
if (x == en)return flow;
ll sum = 0;
for (int i = head[x]; i != -1; i = e[i].next) {
ll y = e[i].to;
if (e[i].val != 0 && dep[y] == dep[x] + 1) {
ll tmp = dinic(y, min(e[i].val, flow - sum), en);
e[i].val -= tmp;
e[i ^ 1].val += tmp;
sum += tmp;
if (sum == flow)return sum;
}
}
return sum;
}
void solve() {
cin >> m >> n;
init();
ll x, y;
while (cin >> x >> y) {
if (x == -1 && y == -1)break;
addxy(x, y, 1);
}
for (int i = 1; i <= m; i++) {
addxy(0, i, 1);
}
for (int i = m + 1; i <= n; i++) {
addxy(i, n + 1, 1);
}
ll ans = 0;
while (makelevel(0,n+1)) {
ans += dinic(0, LLONG_MAX, n + 1);
}
cout << ans << "\n";
for (int i = 1; i <= m; i++) {
for (int j = head[i]; j != -1; j = e[j].next) {
ll y = e[j].to;
if (y != 0 && e[j].val == 0 && e[j ^ 1].val == 1) {
cout << i << " " << y << "\n";
}
}
}
}P3254 圆桌问题
建模方式
每个组织要出ri个代表，那么我们就将超级源点与这m个公司连上，流量设置为ri。同理，我们把每个桌子与超级终点连接，流量设置为ci。然后跑最大流。如果最大流等于人数，则这些人肯定有位置做。否则我们就输出0。答案输出，按照每个公司与桌子连接的反向边的流量判断即可，若反向流量不为0，则肯定存在人坐。
代码实现
ll n, m;
struct edge {
ll next;
ll to;
ll val;
}e[210000];
ll head[210000];
ll cnt = 0;
void init() {
cnt = 0;
for (int i = 1; i <= n + m; i++) {
head[i] = -1;
}
head[0] = head[n + m + 1] = -1;
}
void add(ll x, ll y, ll val) {
e[cnt].next = head[x];
e[cnt].to = y;
e[cnt].val = val;
head[x] = cnt++;
}
void addxy(ll x, ll y, ll val) {
add(x, y, val);
add(y, x, 0);
}
ll dep[210000];
bool makelevel(ll be, ll en) {
memset(dep, 0, sizeof dep);
queue<ll>q;
q.push(be); dep[be] = 1;
while (q.size()) {
ll x = q.front(); q.pop();
if (x == en)return true;
for (int i = head[x]; i != -1; i = e[i].next) {
ll y = e[i].to;
if (dep[y] == 0 && e[i].val != 0) {
q.push(y);
dep[y] = dep[x] + 1;
}
}
}
return false;
}
ll dinic(ll x, ll flow, ll en) {
if (x == en)return flow;
ll sum = 0;
for (int i = head[x]; i != -1; i = e[i].next) {
ll y = e[i].to;
if (e[i].val != 0 && dep[y] == dep[x] + 1) {
ll tmp = dinic(y, min(e[i].val, flow - sum), en);
e[i].val -= tmp;
e[i ^ 1].val += tmp;
sum += tmp;
if (sum == flow)return sum;
}
}
return sum;
}
void solve() {
cin >> m >> n;
init();
ll sum = 0;
for (int i = 1; i <= m; i++) {
ll val; cin >> val; sum += val;
addxy(0, i, val);
for (int j = m + 1; j <= m + n; j++) {
addxy(i, j, 1);
}
}
for (int i = m + 1; i <= m + n; i++) {
ll val; cin >> val;
addxy(i, n + m + 1, val);
}
ll ans = 0;
while(makelevel(0,n+m+1)){
ans += dinic(0, LLONG_MAX, n + m + 1);
}
if (ans == sum) {
cout << "1\n";
for (int i = 1; i <= m; i++) {
for (int j = head[i]; j != -1; j = e[j].next) {
ll y = e[j].to;
if (y != 0 && e[j ^ 1].val != 0) {
cout << y - m << " ";
}
}
cout << "\n";
}
}
else {
cout << "0\n";
}
}P2754 家园/星际转移问题
建模方式
并查集判断是否存在方案。
分层图思想，按照每一天的状态依次建立网络流图：
-
每一个空间站与他的下一天连接INF大小的边。
-
按照每一天的转移，连接上一天与下一天要转移到的位置。
然后每一天都跑一次dinic求最大流，然后得出当最终流量大于k的时候输出天数。
代码实现
//写爆了，先鸽了
P2774 方格取数问题
建模方式
ans=权值和-最小割=权值和-最大流（数值上）。
我们可以知道相邻的数是不能取的，所以将格子化为黑白棋盘，然后将黑白棋子连边，并且将流量设置最大。
我们在求取最大流的时候，如果有流量经过的话，意味着我们这两个棋子是必然不能选的。所以，我们只需要求取所有棋子的权值和，然后减上最大流，即使取值最大的方法。
代码实现
ll n, m;
struct edge {
ll next;
ll to;
ll val;
}e[210000];
ll head[210000];
ll cnt = 0;
ll id(ll x, ll y) {
return (x - 1) * m + y + 1;
}
void init() {
cnt = 0;
memset(head, -1, sizeof(head));
}
void add(ll x, ll y, ll val) {
e[cnt].next = head[x];
e[cnt].to = y;
e[cnt].val = val;
head[x] = cnt++;
}
void addxy(ll x, ll y, ll val) {
add(x, y, val);
add(y, x, 0);
}
ll dep[210000];
bool makelevel(ll be, ll en) {
memset(dep, 0, sizeof dep);
queue<ll>q;
q.push(be); dep[be] = 1;
while (q.size()) {
ll x = q.front(); q.pop();
if (x == en)return true;
for (int i = head[x]; i != -1; i = e[i].next) {
ll y = e[i].to;
if (dep[y] == 0 && e[i].val != 0) {
q.push(y);
dep[y] = dep[x] + 1;
}
}
}
return false;
}
ll dinic(ll x, ll flow, ll en) {
if (x == en)return flow;
ll sum = 0;
for (int i = head[x]; i != -1; i = e[i].next) {
ll y = e[i].to;
if (e[i].val != 0 && dep[y] == dep[x] + 1) {
ll tmp = dinic(y, min(e[i].val, flow - sum), en);
e[i].val -= tmp;
e[i ^ 1].val += tmp;
sum += tmp;
if (sum == flow)return sum;
}
}
return sum;
}
ll fx[4][2] = { {1,0},{0,1},{-1,0},{0,-1} };
void solve() {
cin >> n >> m; init();
ll sum = 0;
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= m; j++) {
ll x; cin >> x; sum += x;
if ((i + j) % 2 == 0) {
addxy(0, id(i, j), x);
for (int k = 0; k < 4; k++) {
ll ii = i + fx[k][0];
ll jj = j + fx[k][1];
if (ii<1 || ii>n || jj<1 || jj>m)continue;
addxy(id(i, j), id(ii, jj), LLONG_MAX);
}
}
else {
addxy(id(i, j), 1, x);
}
}
}
while (makelevel(0, 1)) {
sum -= dinic(0, LLONG_MAX, 1);
}
cout << sum << "\n";
}P4015 运输问题
建模方法
最小费用最大流问题。
将源点和所有仓库连接，连接容量为a[i]花费为0的边，表示可以运送a[i]个物品。
将所有货物与汇点连接，连接容量为b[i]花费为0的边，表示可以卖出b[i]个物品。
中间按照给定的每个边的花费，我们将所有连接，按照他们的花费连接。
然后跑一遍最小费用流即可。
代码实现
struct edge {
ll next;
ll to;
ll val;
ll cost;
}e[210000];
ll head[210000];
ll cnt = 0;
void init() {
cnt = 0;
memset(head, -1, sizeof head);
}
void add(ll x, ll y, ll val,ll cost) {
e[cnt].next = head[x];
e[cnt].to = y;
e[cnt].val = val;
e[cnt].cost = cost;
head[x] = cnt++;
}
void addxy(ll x, ll y, ll val, ll cost) {
add(x, y, val, cost);
add(y, x, 0, -cost);
}
ll pre[210000];
ll dis[210000];
bool vis[210000];
ll n, m;
bool spfa(ll s, ll t) {
memset(vis, false, sizeof vis);
memset(dis, 0x7f, sizeof dis);
memset(pre, -1, sizeof pre);
dis[s] = 0;
vis[s] = true;
queue<ll>q;
q.push(s);
while (q.size()) {
ll u = q.front(); q.pop();
vis[u] = false;
for (int i = head[u]; i != -1; i = e[i].next) {
ll v = e[i].to;
if (e[i].val!=0 && dis[v] > dis[u] + e[i].cost) {
dis[v] = dis[u] + e[i].cost;
pre[v] = i;
if (!vis[v]) {
vis[v] = true;
q.push(v);
}
}
}
}
if (pre[t] == -1)return false;
else return true;
}
//返回最大流，cost存最小费用
ll minCostMaxFlow(ll s, ll t, ll& cost) {
ll flow = 0; cost = 0;
while (spfa(s, t)) {
ll Min = LLONG_MAX;
for (int i = pre[t]; i != -1; i = pre[e[i^1].to]) {
Min = min(Min, e[i].val);
}
for (int i = pre[t]; i != -1; i = pre[e[i^1].to]) {
e[i].val -= Min;
e[i ^ 1].val += Min;
cost += e[i].cost * Min;
}
flow += Min;
}
return flow;
}
void solve() {
cin >> m >> n;
init();
vector<ll>a(m+1);
vector<ll>b(n+1);
vector<vector<ll>>ab(m + 1,vector<ll>(n + 1));
for (int i = 1; i <= m; i++) {
cin >> a[i];
addxy(0, i, a[i], 0);
}
for (int i = 1; i <= n; i++) {
cin >> b[i];
addxy(i + m, n + m + 1, b[i], 0);
}
for (int i = 1; i <= m; i++) {
for (int j = 1; j <= n; j++) {
cin >> ab[i][j];
addxy(i, j + m, LLONG_MAX, ab[i][j]);
}
}
ll cost = 0;
ll flow = minCostMaxFlow(0, n + m + 1, cost);
cout << cost << "\n";
init();
for (int i = 1; i <= m; i++) {
addxy(0, i, a[i], 0);
}
for (int i = 1; i <= n; i++) {
addxy(i + m, n + m + 1, b[i], 0);
}
for (int i = 1; i <= m; i++) {
for (int j = 1; j <= n; j++) {
addxy(i, j + m, LLONG_MAX, -ab[i][j]);
}
}
cost = 0;
flow = minCostMaxFlow(0, n + m + 1, cost);
cout << abs(cost) << "\n";
}