辽宁城乡住房建设厅网站,音乐分享网站源码,北京免费公司注册地址,网站怎么做更新吗没有想到网络流还能解决这一类问题#xff0c;完全想不到_ 一开始把所有的无向边制定任意方向有当做有向边看#xff0c;然后统计每个点的入度和出度。以前有向图的欧拉回路判定是每个点的入读都等于出度#xff0c;这样可以保证可以回到起点#xff0c;现在在一些边可以调…没有想到网络流还能解决这一类问题完全想不到_ 一开始把所有的无向边制定任意方向有当做有向边看然后统计每个点的入度和出度。以前有向图的欧拉回路判定是每个点的入读都等于出度这样可以保证可以回到起点现在在一些边可以调换方向的情况下所有定点的入度和出度之差必定为偶数因为调换任意一条边的方向都会使两个定点的入度和出度变化2所以要构成一个欧拉回路所有点的入度和出度之差都为偶数并设差为deg。 现在问题转化成了能否通过改变一些边的方向来是的所有点的入度出度都为0因为有向边的方向已经确定不用理会把他们全部都删去。剩下的边中如果有出度大于入度的肯定要调换-deg/2条边来使其变成0建立源点到这些点的边容量为-deg/2同理有出入大于入度的就建立这些点到汇点的边容量同样为deg/2。其他的边容量都为1然后做一遍最大流如果流量和需要调换的边数相等即源点出去的边全部都满载就有欧拉回路存在否则不存在欧拉回路。 为什么这样子是成立的我的想法是这样的除了连接源点和汇点的边之外其他的边的容量都为11的流量对应的就是一条边源点连接到一个点的时候的容量为t如果满载相当于这个点出发的t条边满载相当于调换了t条边但是这样子会影响后面的边的度不过因为流会一直流到汇点中途所有的满载的边都是要调换的所以中间原本度为0的点的度其实到最后不会改变。 #include cstdio
#include cstring
#include cmath
#include algorithm
#include climits
#include string
#include iostream
#include map
#include cstdlib
#include list
#include set
#include queue
#include stackusing namespace std;typedef long long LL;
const int maxn 205;
const int INF INT_MAX / 3;struct Edge {int u,v,cap;Edge(int u,int v,int cap):u(u),v(v),cap(cap) {}
};int n,m,incnt[maxn],outcnt[maxn];
int deg[maxn],s,t;
vectorEdge edges;
vectorint e[maxn];void adde(int u,int v,int w) {int m edges.size();edges.push_back(Edge(u,v,w));edges.push_back(Edge(v,u,0));e[u].push_back(m);e[v].push_back(m ^ 1);
}int level[maxn],q[maxn * 2],qs,qe;
bool bfs() {//建立层次网络memset(level,0,sizeof(level));level[s] 1;qs qe 0;q[qe] s;while(qs qe) {int now q[qs],nm e[now].size();if(now t) break;for(int i 0;i nm;i) {Edge ne edges[e[now][i]];if(ne.cap level[ne.v] 0) {level[ne.v] level[now] 1;q[qe] ne.v;}}}return level[t];
}int dfs(int now,int alpha) {if(now t) return alpha;int sum 0,nm e[now].size();for(int i 0;i nm;i) {Edge ne edges[e[now][i]];if(level[now] 1 level[ne.v] ne.cap alpha) {int ret dfs(ne.v,min(alpha,ne.cap));ne.cap - ret; edges[e[now][i] ^ 1].cap ret;sum ret; alpha - ret;}}if(sum 0) level[now] -1;return sum;
}void dinic() {while(bfs()) dfs(s,INF);
}bool solve() {s 0; t n 1;//判断入度出度之差是否为偶数for(int i 1;i n;i) {deg[i] incnt[i] - outcnt[i];if(deg[i] 1) return false;}//建立容量网络for(int i 1;i n;i) {//如果入度小于出度,建立从起点到这个点的边容量为deg/2if(deg[i] 0) adde(s,i,-deg[i] / 2);//如果出度大于入读建立从当前点到汇点的边容量同样为deg/2if(deg[i] 0) adde(i,t,deg[i] / 2);}//计算最大流dinic();//判断从源点出发的所有边是否满流int m e[s].size();for(int i 0;i m;i) {if(edges[e[s][i]].cap ! 0) return false;}return true;
}int main() {int T; scanf(%d,T);while(T--) {scanf(%d%d,n,m);edges.clear();for(int i 0;i n 1;i) e[i].clear();memset(incnt,0,sizeof(incnt));memset(outcnt,0,sizeof(outcnt));for(int i 1;i m;i) {int u,v,c; scanf(%d%d%d,u,v,c);//先将无向边全部作为有向边处理incnt[v]; outcnt[u];//无向边存起来if(c 0) adde(u,v,1);}if(solve()) puts(possible);else puts(impossible);}return 0;
}转载于:https://www.cnblogs.com/rolight/p/3871431.html
