网站建设方案内容,google浏览器网页版,中职学校网站建设情况总结,多说wordpress【题意】在一个无向图中#xff0c;一个人要从A点赶往B点#xff0c;之后再赶往C点#xff0c;且要求中途不能多次经过同一个点。问是否存在这样的路线。#xff08;3 N 30011, 1 M 50011#xff09; 【思路】很巧的一道题#xff0c;一般我们都是把…【题意】在一个无向图中一个人要从A点赶往B点之后再赶往C点且要求中途不能多次经过同一个点。问是否存在这样的路线。3 N 30011, 1 M 50011 【思路】很巧的一道题一般我们都是把源点连接起点但那样的话就不好控制从A先到B再到C了所以我们换个思路以B为源点A、C为汇点看最大流是否为2即可~不经过同一个点就直接拆点连一条(i, i, 1)即可无向图……就连两条反向边吧~~本来想改一下反向流就好的可是想想那样也把源点汇点连出来的边也变成双向了……没试行不行……
#include
#include
#include
#include
#include
#include
#define MID(x,y) ((xy)/2)
#define mem(a,b) memset(a,b,sizeof(a))
using namespace std;
const int MAXV 60055;
const int MAXE 200055;
const int oo 0x3fffffff;
struct node{int u, v, flow;int opp;int next;
};
struct Dinic{node arc[2*MAXE];int vn, en, head[MAXV]; //vn点个数(包括源点汇点),en边个数int cur[MAXV]; //当前弧int q[MAXV]; //bfs建层次图时的队列int path[2*MAXE], top; //存dfs当前最短路径的栈int dep[MAXV]; //各节点层次void init(int n){vn n;en 0;mem(head, -1);}void insert_flow(int u, int v, int flow){arc[en].u u;arc[en].v v;arc[en].flow flow;arc[en].opp en 1;arc[en].next head[u];head[u] en ;arc[en].u v;arc[en].v u;arc[en].flow 0; //反向弧arc[en].opp en - 1;arc[en].next head[v];head[v] en ;}bool bfs(int s, int t){mem(dep, -1);int lq 0, rq 1;dep[s] 0;q[lq] s;while(lq rq){int u q[lq ];if (u t){return true;}for (int i head[u]; i ! -1; i arc[i].next){int v arc[i].v;if (dep[v] -1 arc[i].flow 0){dep[v] dep[u] 1;q[rq ] v;}}}return false;}int solve(int s, int t){int maxflow 0;while(bfs(s, t)){int i, j;for (i 1; i vn; i ) cur[i] head[i];for (i s, top 0;;){if (i t){int mink;int minflow 0x3fffffff;for (int k 0; k top; k )if (minflow arc[path[k]].flow){minflow arc[path[k]].flow;mink k;}for (int k 0; k top; k )arc[path[k]].flow - minflow, arc[arc[path[k]].opp].flow minflow;maxflow minflow;top mink; //arc[mink]这条边流量变为0, 则直接回溯到该边的起点即可(这条边将不再包含在增广路内).i arc[path[top]].u;}for (j cur[i]; j ! -1; cur[i] j arc[j].next){int v arc[j].v;if (arc[j].flow dep[v] dep[i] 1)break;}if (j ! -1){path[top ] j;i arc[j].v;}else{if (top 0) break;dep[i] -1;i arc[path[-- top]].u;}}}return maxflow;}
}dinic;
int main(){int t;scanf(%d,t);while(t --){int n, m;scanf(%d %d, n, m);if (n 3){puts(NO);continue;}dinic.init(2*n2);for (int i 1; i n; i ){dinic.insert_flow(2*i-1, 2*i, 1);}for (int i 1; i m; i ){int u, v;scanf(%d %d, u, v);if(u n || v n) continue;dinic.insert_flow(2*u, 2*v-1, 1);dinic.insert_flow(2*v, 2*u-1, 1);}dinic.insert_flow(2*n1, 2*2, 2);dinic.insert_flow(2*1, 2*n2, 1);dinic.insert_flow(2*3, 2*n2, 1);if (dinic.solve(2*n1, 2*n2) 2){puts(YES);}else{puts(NO);}}return 0;
}转载于:https://www.cnblogs.com/AbandonZHANG/p/4114048.html
