cf1610f Mashtali: a Space Oddysey
给定一张含 \(n\) 个点 \(m\) 条边的无向图，结点编号为 \(1\) 到 \(n\) 。
每条边有边权 \(w_i\) ，而 \(w_i\) 只能等于 \(1\) 或 \(2\) 。蓝想要给每条边定向，使得图尽可能的可爱。
图的可爱程度定义为图中好的结点的数量。一个结点 \(v\) 是好的，当且仅当令 \(d^+(v)\) 为 \(v\) 所有出边的权值和，令 \(d^-(v)\) 为 \(v\) 所有入边的权值和，有 \(|d^+(x)-d^-(x)|=1\) 。
试着帮蓝找到图的最大可能可爱程度，并且给出任意一种构造方案。
输入中，蓝会在第一行给出 \(n\) 和 \(m\) ，之后 \(m\) 行每行依次给出 \(u_i,v_i\) 和 \(w_i\) ，其中前两个数代表边 \(i\) 连接的两个结点，而 \(w_i\) 则代表边 \(i\) 的边权。
输出中，在第一行，你应该输出图的最大可能可爱程度。在输出的第二行，为了告诉蓝你的构造方案，你需要给出一个字符串 \(s\) ，其中若 \(s_i=1\) ，则代表边 \(i\) 被定向为从 \(u_i\) 到 \(v_i\) ，而 \(s_i=2\) 则代表边 \(i\) 被定向为从 \(v_i\) 到 \(u_i\)。
\(1\leq n,m\leq 3\times 10^5,1\leq u_i,v_i\leq n,w_i\in\{1,2\}\)
首先观察得到只有度数为奇数的点才有可能成为好点 .
其次，猜测能构造一种方案使得图中所有的度数为奇数的点都为好点 .
然后，然后，我就不会做了 .
sol1
发现还没有运用 \(w_i\in\{1,2\}\) 这个性质，所以肯定有哪些地方没有考虑到 .
这个图太复杂了，不存在任何一种除了边权为 \(1/2\) 之外的性质，考虑把这个图稍微缩小一下，变成一个比较简单的图 .
观察得到，如果 \(x\to y\to z\) 中，\(x\to y\) 和 \(y\to z\) 的权值是相同的，那么，可以简化成一条边 \(x\to z\) . 简而言之，\(x\to y\to z\) 严格强于 \(x\to z\) .
如果 \(x=z\) ，那么，就是一个自环，考虑 \(x\to y\) 和 \(y\to x\) 即可 .
考虑缩到不存在上面这样的 \(3\) 个点，原图严格强于当前图，但是当前图会显示出原图没有的一些特性 .
此时，观察得到，当前图是一个 \(n\) 个点，变数不超过 \(n\) 的图 . 因为图中只会出现边权为 \(12\) 交替的环或者是链 .
对于环和链来说，之间按照一个方向定向，得到的图，每个度数为奇数的点都可以被满足 .
考虑将缩边后的点的方向传递给每条边即可 . 代码实现上有点难写 .
时间复杂度 : \(O(n+m\log m)\)
空间复杂度 : \(O(n+m)\)
code
#include
using namespace std;
const int inf=1e9+10;
int n,m,cnt=0;
int w[100010],sum[100010];
vector >e;
set >g[2][100010];
set >::iterator it1,it2,it;
priority_queue > >q;
int ls[200010],rs[200010];
bool vis[100010];
int ans[200010];
inline void ae(int id,int dir){
if(id<0)id=-id,dir=1-dir;
ans[id]=3;
if(id<=m){
if(dir==0)ans[id]=1;
else ans[id]=2;
return;
}
if(ls[id]!=inf)ae(ls[id],dir);
if(rs[id]!=inf)ae(rs[id],dir);
}
void dfs(int x){
vis[x]=true;
for(set >::iterator nit=g[0][x].begin();nit!=g[0][x].end();nit++){
int to=nit->first,id=nit->second;
if(!vis[to]){
ae(id,0);
dfs(to);
}
else if(!ans[abs(id)]){
ae(id,0);
}
}
for(set >::iterator nit=g[1][x].begin();nit!=g[1][x].end();nit++){
int to=nit->first,id=nit->second;
if(!vis[to]){
ae(id,0);
dfs(to);
}
else if(!ans[abs(id)]){
ae(id,0);
}
}
}
int main(){
ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
cin>>n>>m;cnt=m;
for(int i=0;i>u>>v>>w[i+1];
u--;v--;
g[w[i+1]-1][u].insert(make_pair(v,i+1));
g[w[i+1]-1][v].insert(make_pair(u,-(i+1)));
e.push_back(make_pair(u,v));
sum[u]+=w[i+1];
sum[v]+=w[i+1];
}
for(int i=0;i1){
it1=it2=g[c][x].begin();it2++;
int y=it1->first,idy=it1->second;
int z=it2->first,idz=it2->second;
if(it1->first==it2->first){
ae(it1->second,0);
ae(it2->second,1);
}else{
++cnt;
g[c][y].insert(make_pair(z,cnt));
g[c][z].insert(make_pair(y,-cnt));
ls[cnt]=-idy;
rs[cnt]=idz;
}
g[c][y].erase(make_pair(x,-idy));
g[c][z].erase(make_pair(x,-idz));
g[c][x].erase(*it1);
g[c][x].erase(*it2);
q.push(make_pair((int)g[c][y].size(),make_pair(y,c)));
q.push(make_pair((int)g[c][z].size(),make_pair(z,c)));
}
}
for(int i=0;i
sol2
看到度数奇数偶数，可以想到欧拉图 . 还是同样的道理，这个图太复杂了，没有什么性质 .
考虑用欧拉图缩边，将边权为 \(1\) 的边建立一个图，将边权为 \(2\) 的边建立一个图 . 然后进行锁边 .
但是无向欧拉图必须是所有点的度数为偶数，那么，考虑建立一个总点 \(s\) ，对于所有度数为奇数的点连一条边 . 用修改后的图跑欧拉回路 . 但是这些 \(s\) 所连的边是不存在的，考虑断掉，剩下的就是一些权值相同的链，考虑所称一条边 .
对两个图分别缩边之后便可以得到 \(12\) 交替的环和链 . 考虑直接一个方向定向 .
时间复杂度 : \(O(n+m)\)
空间复杂度 : \(O(n+m)\)
code
#include
#define inf 1000000010
using namespace std;
int n,m,cnt=0,ecnt=0;
int sum[100010];
vector >E;
vector >g1[100010],g2[100010];
vector >e1[100010],e2[100010];
int iter[100010];
bool vis[300010],mark[300010];
vectorv;
vector >e;
int ans[100010];
void euler1(int x){
mark[x]=true;
for(int&i=iter[x];i<(int)g1[x].size();i++){
int to=g1[x][i].first,id=g1[x][i].second;
if(vis[abs(id)])continue;
vis[abs(id)]=true;
euler1(to);
v.push_back(-id);
}
}
void dfs1(int x){
mark[x]=true;
for(int&i=iter[x];i<(int)g1[x].size();i++){
int to=g1[x][i].first,id=g1[x][i].second;
if(vis[abs(id)])continue;
vis[abs(id)]=true;
if(id>0)ans[id]=1;
else ans[-id]=2;
dfs1(to);
}
}
void euler2(int x){
mark[x]=true;
for(int&i=iter[x];i<(int)g2[x].size();i++){
int to=g2[x][i].first,id=g2[x][i].second;
if(vis[abs(id)])continue;
vis[abs(id)]=true;
euler2(to);
v.push_back(-id);
}
}
void dfs2(int x){
mark[x]=true;
for(int&i=iter[x];i<(int)g2[x].size();i++){
int to=g2[x][i].first,id=g2[x][i].second;
if(vis[abs(id)])continue;
vis[abs(id)]=true;
if(id>0)ans[id]=1;
else ans[-id]=2;
dfs2(to);
}
}
void dfs(int x){
mark[x]=true;
for(int i=0;i<(int)e1[x].size();i++){
int to=e1[x][i].first,id=e1[x][i].second;
if(!vis[abs(id)]){
vis[abs(id)]=true;
int jd=0;
if(id<0)jd++,id=-id;
id--;
for(int j=0;j<(int)e[id].size();j++){
int njd=jd;
if(e[id][j]<0)njd++,e[id][j]=-e[id][j];
if(njd==1)ans[e[id][j]]=2;
else ans[e[id][j]]=1;
}
dfs(to);
}
}
for(int i=0;i<(int)e2[x].size();i++){
int to=e2[x][i].first,id=e2[x][i].second;
if(!vis[abs(id)]){
vis[abs(id)]=true;
int jd=0;
if(id<0)jd++,id=-id;
id--;
for(int j=0;j<(int)e[id].size();j++){
int njd=jd;
if(e[id][j]<0)njd++,e[id][j]=-e[id][j];
if(njd==1)ans[e[id][j]]=2;
else ans[e[id][j]]=1;
}
dfs(to);
}
}
}
int main(){
ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
cin>>n>>m;
E.push_back({0,0});
for(int i=1;i<=m;i++){
int u,v,w;
cin>>u>>v>>w;
u--;v--;
sum[u]+=w;
sum[v]+=w;
if(w==1){
g1[u].push_back(make_pair(v,i));
g1[v].push_back(make_pair(u,-i));
}else{
g2[u].push_back(make_pair(v,i));
g2[v].push_back(make_pair(u,-i));
}
E.push_back(make_pair(u,v));
}
ecnt=m;
for(int i=0;ivec;
for(int j=i;j<(int)v.size();j++){
int id=v[j];
if(s==-1){
if(id<0)s=E[-id].first;
else s=E[id].second;
}else{
if(E[abs(id)].first==n||E[abs(id)].second==n){
if(id<0)t=E[-id].second;
else t=E[id].first;
i=j;
break;
}
vec.push_back(id);
}
}
++cnt;
e1[s].push_back(make_pair(t,cnt));
e1[t].push_back(make_pair(s,-cnt));
e.push_back(vec);
}
for(int i=0;ivec;
for(int j=i;j<(int)v.size();j++){
int id=v[j];
if(s==-1){
if(id<0)s=E[-id].first;
else s=E[id].second;
}else{
if(E[abs(id)].first==n||E[abs(id)].second==n){
if(id<0)t=E[-id].second;
else t=E[id].first;
i=j;
break;
}
vec.push_back(id);
}
}
++cnt;
e2[s].push_back(make_pair(t,cnt));
e2[t].push_back(make_pair(s,-cnt));
e.push_back(vec);
}
for(int i=0;i
相关