[ICPC2018西安L] Eventual … Journey - 结论
Description
N个车站,M条边,每个车站分为黑白两种,如果两个点颜色一样,可以花1的花费到达,或者两个点有边直接连接,问每个点可以到达的点的总花费的最小值
Solution
直接相连或者同类代价为 1,两点度数都为 0 代价为 3,其它情况代价为 2
#include <bits/stdc++.h>
using namespace std;
#define int long long
const int N = 1e5 + 5;
int n, m, a[N], c[2], d[2];
vector<int> g[N];
signed main()
{
ios::sync_with_stdio(false);
cin >> n >> m;
for (int i = 1; i <= n; i++)
cin >> a[i];
for (int i = 1; i <= m; i++)
{
int u, v;
cin >> u >> v;
if (a[u] == a[v])
continue;
g[u].push_back(v);
g[v].push_back(u);
}
for (int i = 1; i <= n; i++)
c[a[i]]++;
for (int i = 1; i <= n; i++)
if (g[i].size() == 0)
d[a[i]]++;
if (m == 0)
{
for (int i = 1; i <= n; i++)
cout << n - 1 << " ";
return 0;
}
for (int i = 1; i <= n; i++)
{
if (g[i].size() > 0)
{
cout << n - 1 + c[1 - a[i]] - g[i].size() << " ";
}
else
{
cout << n - 1 + c[1 - a[i]] + d[1 - a[i]] << " ";
}
}
}