S+二分图与网络流初步
A. 生成二分图
最开始理解错了题意写了一个$O(n^2)$的算法直接炸开了😅
感谢ooliver救我一命（
正解的话是bfs染色并统计两边大小，计算答案：
$$
ans=\sum [v_1 v_2+\frac{(v_1+v_2)\times(n-v_1-v_2)}{2}] – m
$$
最好记得开个 long long (awa
还有记得判断无解的时候要看两个是不是都为0不然炸了（
#include<bits/stdc++.h>
using namespace std;
#define intc const int
#define int long long
#define Cios ios::sync_with_stdio(0);cin.tie(0);cout.tie(0)
intc N=2e5+10;
int n,m,ans=0,cl[N];
vector<int> g[N];
pair<int,int> bfs(int x) {
int v1=0,v2=0;
queue<int> q;
q.push(x);
cl[x]=1;
v1++;
while (q.size()) {
int u=q.front();
q.pop();
for (int v:g[u]) {
if (cl[v]) {
if (cl[v]!=cl[u]) continue;
return make_pair(0,0);
}
if (cl[u]==1) {
v2++;
cl[v]=2;
}
else {
v1++;
cl[v]=1;
}
q.push(v);
}
}
return make_pair(v1*v2,v1+v2);
}
signed main() {
cin>>n>>m;
for (int i=1;i<=m;i++) {
int u,v;
cin>>u>>v;
g[u].push_back(v);
g[v].push_back(u);
}
for (int i=1;i<=n;i++) {
if (!cl[i]) {
pair<int,int> v=bfs(i);
if (v.first==0&&v.second==0) {
cout<<0;
return 0;
}
ans+=v.first*2+v.second*(n-v.second);
//cerr<<v.first<<" "<<v.second<<endl;;
}
}
cout<<ans/2-m<<endl;
return 0;
}B. 图上同色最远(ARC165 C)
先按二分图染色考虑；
不难发现（并非不难），若给定的图是二分图，按二分图染色得到的答案为图上所有三个点的路径长度最小值；
考虑非二分图，显然奇环上必有相邻同色点。故答案又有了一个新的上界：所有奇环边权最大值的最小值。
考虑如何得到所有奇环边权最大值的最小值，将边按边权从小到大排序，在并查集判二分图时，若发现连上这条边会出现奇环，就将上界与当前边权取 min，并取消连边即可。
#include<bits/stdc++.h>
using namespace std;
#define intc const int
#define int long long
#define Cios ios::sync_with_stdio(0);cin.tie(0);cout.tie(0)
intc N=2e5+5;
int n,m,ans=INT_MAX,fi[N],se[N],fa[N<<1];
struct edge {
int u,v,w;
}e[N];
int get(int x) {
return x==fa[x]?x:fa[x]=get(fa[x]);
}
signed main() {
Cios;
memset(fi,0x3f,sizeof fi);
memset(se,0x3f,sizeof se);
cin>>n>>m;
for(int i=1;i<=m;i++) {
int u,v,w;
cin>>u>>v>>w;
e[i]={u,v,w};
if (w<fi[u]) {
se[u]=fi[u];
fi[u]=w;
}
else if (w<se[u]) se[u]=w;
if (w<fi[v]) {
se[v]=fi[v];
fi[v]=w;
}
else if (w<se[v]) se[v]=w;
}
for (int i=1;i<=n<<1;i++) fa[i]=i;
for (int i=1;i<=n;i++) ans=min(ans,se[i]+fi[i]);
sort(e+1,e+m+1,[](edge a,edge b) {return a.w<b.w;});
for (int i=1;i<=m;i++) {
if (get(e[i].u)==get(e[i].v)) ans=min(ans,e[i].w);
else fa[get(e[i].u)]=get(e[i].v+n),fa[get(e[i].v)]=get(e[i].u+n);
}
cout<<ans;
return 0;
}
评论（0）
暂无评论