h5营销型网站suteng,哪个软件可以看街景,做影视网站什么cms好用吗,如何建设一个自己的网站首页感觉智商还是不太够#x1f605;
正常人的做法#xff1a;答案上界是显然的#xff0c;就是 ∑ w \sum w ∑w为奇数的点的个数#xff0c;因为限制很松。但是直接构造比较棘手#xff0c;考虑两条边 ( x , v ) (x,v) (x,v)和 ( v , y ) (v,y) (v,y)#xff0c;如果这两条…感觉智商还是不太够
正常人的做法答案上界是显然的就是 ∑ w \sum w ∑w为奇数的点的个数因为限制很松。但是直接构造比较棘手考虑两条边 ( x , v ) (x,v) (x,v)和 ( v , y ) (v,y) (v,y)如果这两条边的权值也相同那么可以在原图中将 ( x , v ) (x,v) (x,v)和 ( v , y ) (v,y) (v,y)删掉然后加入 ( x , y ) (x,y) (x,y)这条边。这样每次操作后边的数目会减少 1 1 1。一直这样操作下去最后每个点的度数不会超过 2 2 2因此是若干环和链显然从链的端点或者环上任意一点开始定向即可。
具体实现方式是枚举 x x x以及出边 v v v然后再找到 v v v的一条出边 y y y将 ( x , v ) (x,v) (x,v)和 ( v , y ) (v,y) (v,y)删掉加入边 ( x , y ) (x,y) (x,y)然后 v v v赋值成 y y y继续寻找 y y y的出边。写代码的时候要先把 ( x , v ) (x,v) (x,v)这条边删掉直到 x x x的所有出边都扩展完了过后再加回来。最后还原方案只需建立二叉树然后从根节点开始遍历即可和 kruskal \text{kruskal} kruskal重构树比较类似。
复杂度 O ( n m ) O(nm) O(nm)。但是比较难写估计要调半天。
聪明人的做法考虑欧拉回路。本质上就是利用了回路上出边和入边数目相同来构造但是这道题的建图方式比较难。
考虑建立 2 n 1 2n1 2n1个点因为 1 1 1和 2 2 2其实本质上是对称的所以把点复制一遍建边方式如下 1.1 1.1 1.1 对于边权为 1 1 1的边 ( u , v ) (u,v) (u,v)加入边 ( u , v ) (u,v) (u,v) 1.2 1.2 1.2 对于边权为 2 2 2的边 ( u , v ) (u,v) (u,v)加入边 ( u n , v n ) (un,vn) (un,vn) 1.3 1.3 1.3 设 d i ( j ) d_i(j) di(j)表示 j j j连了多少条度为 i i i的边如果 d 1 ( u ) d_1(u) d1(u)和 d 2 ( u ) d_2(u) d2(u)都为奇数加入边 ( u , u n ) (u,un) (u,un)如果只有 d 1 ( u ) d_1(u) d1(u)为奇数加入边 ( u , 2 n 1 ) (u,2n1) (u,2n1)如果只有 d 2 ( u ) d_2(u) d2(u)为奇数加入边 ( u n , 2 n 1 ) (un,2n1) (un,2n1)
跑欧拉回路然后根据前两类边的方向就可以确定原图中边的方向。
代码很简单。但是确实比较难想到
我是小丑所以写了第一种做法。
#includebits/stdc.h
#define ll long long
#define fi first
#define se second
#define pb push_back
using namespace std;
const int N6e55;
int n,m,ok[N],vs[N],vs2[N],U[N],V[N],W[N],du[N],du2[N],cnt,tot;
pairint,intans[N];
vectorints[N][2];
vectorintvec;
vectorintG[N];
vectorintG2[N];
int get(int x,int y){if(yU[x])return V[x];return U[x];
}
void dfs(int i,int pre,int j){while(s[i][j].size()vs[s[i][j].back()]){s[i][j].pop_back();}if(s[i][j].size()0){vec.pb(pre);return;}int ts[i][j].back();vs[t]1,s[i][j].pop_back();cnt,U[cnt]get(pre,i),V[cnt]get(t,i),vs[cnt]1;G[cnt].pb(t),G[cnt].pb(pre),du2[t],du2[pre];dfs(V[cnt],cnt,j);
}
void dfs2(int u){while(G2[u].size()vs2[G2[u].back()])G2[u].pop_back();if(G2[u].size()0)return;int tG2[u].back();G2[u].pop_back();vs2[t]1,ans[t]{u,get(t,u)},dfs2(get(t,u));
}
void dfs3(int u){if(G[u].size()){int lG[u][0],rG[u][1];if(V[l]U[r]){ans[l]{U[l],V[l]},ans[r]{U[r],V[r]};}else if(U[l]U[r]){ans[l]{V[l],U[l]},ans[r]{U[r],V[r]};}else if(V[l]V[r]){ans[l]{U[l],V[l]},ans[r]{V[r],U[r]};}else{ans[l]{V[l],U[l]},ans[r]{V[r],U[r]};}if(ans[l].fi!ans[u].fi){swap(ans[l].fi,ans[l].se);swap(ans[r].fi,ans[r].se);}dfs3(l),dfs3(r);}
}
int main(){ios::sync_with_stdio(false);cin.tie(0),cout.tie(0);cinnm,cntm;for(int i1;im;i){int u,v,w;cinuvw,w--;s[u][w].pb(i),s[v][w].pb(i);if(w0)ok[u]^1,ok[v]^1;U[i]u,V[i]v,W[i]w;}for(int i1;in;i){for(int j0;j2;j){while(1){while(s[i][j].size()vs[s[i][j].back()])s[i][j].pop_back();if(s[i][j].size()0)break;int ts[i][j].back();s[i][j].pop_back();vs[t]1,dfs(get(t,i),t,j);}while(vec.size()){int tvec.back();vec.pop_back();vs[t]0,s[U[t]][j].pb(t),s[V[t]][j].pb(t);}}}for(int i1;in;i){for(int j0;j2;j){while(1){while(s[i][j].size()vs[s[i][j].back()])s[i][j].pop_back();if(s[i][j].size()0)break;int ts[i][j].back();s[i][j].pop_back();vs[t]1;int kget(t,i);du[i],du[k],G2[i].pb(t),G2[k].pb(t);}}}for(int i1;in;i)if(du[i]1)dfs2(i);for(int i1;in;i)dfs2(i);for(int i1;icnt;i)if(du2[i]0)dfs3(i);for(int i1;in;i)totok[i];couttot\n;for(int i1;im;i){if(ans[i].fiU[i])cout1;else cout2;}
}
