A - Amanda Lounges
题意： 有n个机场，m条边,对于每个机场可能需要等候室也可能不需要；如果输入2，代表路线连接的两个机场都需要建立，输入1，代表路线连接的其中一个机场建立（必须）,输入0代表路线连接的两个机场都不可以建立，问你最少建立几个等候室；
思路： 染色法+DFS
是否建立等候室看成是否染色，机场就是图论的点
对于输入2时，输入的两点颜色标记为’2’即可
对于输入1时，输入的两点颜色标记为‘1’即可
对于上面两种情况，染色时如果出现矛盾情况，就直接“impossible”
对于输入1时，输入的两点暂时先标记为‘0’,代表颜色待定
并只对输入1时，输入的两点建边(为了方便下面dfs搜索)
然后此时建立完边后，一定会出现多个封闭的图，里面的点会有很多情况。
此时，将图进行分类，分为两类，分成图中点全是0，和图中有点不是0的
先对存在不是0点的图搜索一遍，因为建立的边都是因为输入1，而建立的，所以当知道其中一个点的颜色时，这个封闭图其他所有点的颜色都可以推导出来.例如：一个点是2,那与这个点相连的点都应该是1，因为连接的点只能有1个等候室。一个点是1，那与这个点相连的点都应该是2，原理如上。
在这个搜索+染色的过程中，如果发现某个点的颜色与相连的点颜色一致，那么说明矛盾，直接退出
再对全是0的图进行染色，此时就需要对这个图的某个点设置一个颜色，要么设置为1，要么设置为2，对这两种情况都搜索一遍+染色,最终取染成1的最小值(实际不用代码搜索两遍，染色成2和染色成1最终形成的2
和1的数量一定是相对的，知道一个就知道另一个情况的，所以直接取最小值即可)
具体见代码注释(思路转自）
#include <bits/stdc++.h>
using namespace std;
#define pi acos(-1)
#define xx first
#define yy second
#define endl "\n"
#define lowbit(x) x & (-x)
#define int long long
#define ull unsigned long long
#define pb push_back
typedef pair<int, int> PII;
typedef pair<double, double> PDD;
#define max(a, b) (((a) > (b)) ? (a) : (b))
#define min(a, b) (((a) < (b)) ? (a) : (b))
#define Ysanqian ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
const int N = 1e6 + 10, M = 1010, inf = 0x3f3f3f3f, mod = 18446, P = 13331;
const double eps = 1e-8;
int n, m;
int color[N];
bool st[N];
vector<int> g[N];
int res, a, b;
bool dfs(int u, int Color, int tag)
{
color[u] = Color;
st[u] = 1;
if (tag) // tag来判断是否是全0染色
{
if (Color == 1) // 记录我们染色的数量一个是1，一个是2，取min即可
a++;
else
b++;
}
else // 如果是1，2色的扩展染色，我们只会去染没有染过的点，且由于二号色一定有机场，所以扩展染色时染成一号色的就不需要休息室了，
// 而二号染色是一定链接者没有休息室的1号染色是一定要休息室的，对答案贡献加一
{
if (Color == 2)
res++;
}
for (auto ed : g[u]) // 经典的二分染色的版子
{
if (color[ed])
{
if (color[ed] == Color)
return false;
}
else if (!dfs(ed, 3 - Color, tag))
return false;
}
return true;
}
void solve()
{
bool flag = 1;
cin >> n >> m;
for (int i = 1; i <= m; i++)
{
int a, b, c;
cin >> a >> b >> c;
if (c == 2) // 都有休息室的染成2
{
if (color[a] == 1 || color[b] == 1)
flag = 0;
color[a] = color[b] = 2;
}
else if (c == 0) // 都没休息室的染成1
{
if (color[a] == 2 || color[b] == 2)
flag = 0;
color[a] = color[b] = 1;
}
else // 待定的建边
{
g[a].pb(b);
g[b].pb(a);
}
}
// 对有1或-1点的图，进行扩散染色
for (int i = 1; i <= n; i++)
{
if (!st[i] && color[i]) // 没有访问过，求以及有色的
{
if (!dfs(i, color[i], 0))
flag = 0;
}
}
// 对于只有0的图，选一个点设置为1，再扩散染色
for (int i = 1; i <= n; i++)
{
if (st[i])
continue;
a = 0, b = 0; // 可能有多个全0的联通分量，a,b,代表2种颜色，我们用最小值即可
if (!dfs(i, 1, 1))
flag = 0;
res += min(a, b);
}
if (flag)
cout << res << endl;
else
cout << "impossible" << endl;
}
signed main()
{
Ysanqian;
int T;
T = 1;
// cin >> T;
while (T--)
solve();
return 0;
}G - Outing
题意：一辆车容量为V，现有n个人，每个人都有一个对应a[i]，表示只有a[i]上车 i才肯上车，问这辆车最多承载多少人。
由于a[i]和i的对应关系 可能存在 树 或者 环 或者 环连着链->树 三种情况，我们可以得知如果存在环 这个环必然是所在树的树根。
为什么环一定是树根呢？
根据本题题意，每一个点最多有一个依赖点，所以每一个点的出度为1，如果联通分量中出现了环，那么环中每一个点的出边必然指向环内的一个点，不会指向环外的点，所以这个环在缩点后出度必然为0。如果该连通分量中存在两个环，那么这两个环因为都没有出度，所以不可能出现由一个环出发走到另一个环的可能(除非相交，但相交就相当于一个环）因为所有结点的出度为1，该联通分量的的任意一个结点都有只有一个路径可走，假设路径A能走到第一个环，B能走到第二个环，路径A和路径B之间必然不连通，所以这两个环必然位于两个联通分量之中。
tarjan缩点之后，我们根据缩点后的图用并查集来合并同一联通分量的点
因此对图求强连通分量，每个树所采纳的人数的【下限——树根的那个强连通分量，上限——全部】，然后对这些树做分组背包求容量V以内的最大人数。
#include <bits/stdc++.h>
using namespace std;
#define pi acos(-1)
#define xx first
#define yy second
#define endl "\n"
#define lowbit(x) x & (-x)
#define int long long
#define ull unsigned long long
#define pb push_back
typedef pair<int, int> PII;
typedef pair<double, double> PDD;
// #define max(a, b) (((a) > (b)) ? (a) : (b))
// #define min(a, b) (((a) < (b)) ? (a) : (b))
#define Ysanqian ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
const int N = 1e6 + 10, M = 1010, inf = 0x3f3f3f3f, mod = 18446, P = 13331;
const double eps = 1e-8;
int f[N], p[N], a[N], stk[N], id[N], siz[N];
int dfn[N], low[N];
int timestamp, top, scc_cnt;
bool is_stk[N];
vector<int> g[N];
map<int, PII> mp;
void tarjan(int u) // 缩点，将强连通分量缩成一个点
{
dfn[u] = low[u] = ++timestamp;
stk[++top] = u;
is_stk[u] = true;
for (auto j : g[u])
{
if (!dfn[j])
{
tarjan(j);
low[u] = min(low[u], low[j]);
}
else if (is_stk[j])
low[u] = min(low[u], low[j]);
}
if (dfn[u] == low[u])
{
int y;
++scc_cnt;
do
{
y = stk[top--];
is_stk[y] = false;
id[y] = scc_cnt; // 记录该点位于那个强联通分量
siz[scc_cnt]++; // 维护强联通分量的大小
} while (y != u);
}
}
int find(int x)
{
if (x != p[x])
p[x] = find(p[x]);
return p[x];
}
void merge(int x, int y)
{
int a = find(x), b = find(y);
if (a == b)
return;
p[b] = a;
}
void solve()
{
int n, m;
cin >> n >> m;
for (int i = 1; i <= n; i++)
{
cin >> a[i];
g[i].pb(a[i]); // 建边
}
for (int i = 1; i <= n; i++)
{
if (!dfn[i]) // 把环进行缩点
tarjan(i);
}
for (int i = 1; i <= n; i++)
p[i] = i;
for (int i = 1; i <= n; i++)
{
int x = id[i], y = id[a[i]]; // 是否在一个联通分量里
merge(x, y); // 合并联通分量，就相当于组分组背包，
/*例如将以下合成一个联通分量
o o
/ / \ (这是个环，那么正如我们所说下限—就是树根的那个强连通分量，上限就是全部的和，这样就形成一个分组背包)
o o-----o
/ /
o o
*/
}
for (int i = 1; i <= scc_cnt; i++) // 统计该组的大小和最小选择人数
{
mp[find(i)].xx = max(mp[find(i)].xx, siz[i]); // mp的int存的强连通分量的编号，pair第一维表示该联通分量的最大体积，第二维表示最大体积
mp[find(i)].yy += siz[i];
}
for (auto ed : mp)
{
for (int j = m; j >= 0; j--)
{
for (int k = ed.yy.xx; k <= ed.yy.yy; k++)
{
if (j >= k)
f[j] = max(f[j], f[j - k] + k);
}
}
}
cout << f[m] << endl;
}
signed main()
{
Ysanqian;
int T;
T = 1;
// cin >> T;
while (T--)
solve();
return 0;
}
