傳送門
1.前置知識
1.最小路徑點覆寫
DAG中選出最小數量的不相交路徑（無公共點），將所有點覆寫，
求法：將DAG中的點拆成出點和入點，構成一個二分圖，
則原圖的最小路徑點覆寫轉化到新圖中：
1.無公共點->每個點最多只有一個出度一個入度 ->…->新圖中的任意兩條邊之間不相交-> 新圖中的邊都是匹配邊，
小結論：每個路徑終點 對應 一個左側非匹配點
<=> 讓左側非匹配點最少 n-m
<=> 讓左側匹配點最多 m
<=> 找最大匹配邊數 m
->二分圖最大匹配數 = 總點數-最小路徑點覆寫
2.最小路徑重復點覆寫
相較于最小路徑點覆寫，取消了無公共點的限制
求法：先做一次傳遞閉包，
原圖G最小路徑重復點覆寫==新圖G’最小路徑點覆寫，
（證明沒怎么看懂 ，wsfw）
2.題意分析
求DAG中 選擇盡可能多的點，使兩點之間不能相互到達，
等價于求最小路徑重復點覆寫，
最小路徑重復點覆寫中的每一條路徑，都只能選擇一個點，
最優解也就是每條路徑都要選一個點，
3.代碼
#include <bits/stdc++.h>
using namespace std;
//-----pre_def----
const double PI = acos(-1.0);
const int INF = 0x3f3f3f3f;
typedef long long LL;
typedef unsigned long long ULL;
typedef pair<int, int> PII;
typedef pair<double, double> PDD;
#define fir(i, a, b) for (int i = (a); i <= (b); i++)
#define rif(i, a, b) for (int i = (a); i >= (b); i--)
#define endl '\n'
#define init_h memset(h, -1, sizeof h), idx = 0;
#define lowbit(x) x &(-x)
//---------------
const int N = 200 + 10, M = 30010;
int n, m;
bool st[N], d[N][N];
int match[N];
bool find(int u) //匈牙利
{
for (int i = 1; i <= n; i++)
{
if (d[i][u] && !st[i])
{
st[i] = true;
int t = match[i];
if (t == 0 || find(t))
{
match[i] = u;
return true;
}
}
}
return false;
}
void init() {}
int main()
{
#ifndef ONLINE_JUDGE
freopen("in.txt", "r", stdin);
freopen("out.txt", "w", stdout);
int StartTime = clock();
#endif
scanf("%d%d", &n, &m);
while (m--)
{
int a, b;
scanf("%d%d", &a, &b);
d[a][b] = true;
}
//傳遞閉包
fir(k, 1, n)
fir(i, 1, n)
fir(j, 1, n)
d[i][j] |= d[i][k] & d[k][j];
//求最大匹配
int res = 0;
fir(i, 1, n)
{
memset(st, 0, sizeof st);
res += find(i);
}
printf("%d\n", n - res);
#ifndef ONLINE_JUDGE
printf("Run_Time = %d ms\n", clock() - StartTime);
#endif
return 0;
}
再戰圖論
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/279336.html
標籤：其他
上一篇：聯合省選 2021 A卷 題解