UVa 563 Crimewave

题目描述题目要求判断是否存在从每个银行位置到城镇边界的互不相交的路径即路径上的节点不能重复使用。城镇为s×as \times as×a的网格银行位于网格内某些交叉点上。每个交叉点只能被一条逃跑路线使用。需要判断是否存在这样的互斥路径集合。输入格式第一行一个整数ppp表示测试用例的数量。每个测试用例的第一行包含三个整数sss、aaa、bbb1≤s,a≤501 \le s, a \le 501≤s,a≤50b≥1b \ge 1b≥1分别表示街道数、大道数和银行数。接下来bbb行每行两个整数xxx、yyy表示银行位置。输出格式对于每个测试用例输出一行possible或not possible。样例输入2 6 6 10 4 1 3 2 4 2 5 2 3 4 4 4 5 4 3 5 4 5 5 5 6 5 3 2 2 3 3 3 4 3 3 4输出possible not possible题目分析本题的核心是节点不相交路径问题可以转化为最大流问题。建模方法将每个网格节点拆分为入点和出点中间连一条容量为111的边表示该节点只能被使用一次。源点连接到每个银行位置入点容量为111。每个节点的出点连接到相邻节点的入点容量为111。边界节点的出点连接到汇点容量为111。求最大流若最大流等于银行数则存在互斥路径。复杂度分析节点数s×a≤2500s \times a \le 2500s×a≤2500边数O(4×O(4 \timesO(4×节点数)))最大流算法可接受。代码实现// Crimewave// UVa ID: 563// Verdict: Accepted// Submission Date: 2017-09-21// UVa Run Time: 0.070s//// 版权所有C2016邱秋。metaphysis # yeah dot net#includebits/stdc.husingnamespacestd;constintMAXV5100,MAXA31000,INF0x7fffffff;structarc{intu,v,capacity,residual,next;};classEdmondsKarp{private:arc*arcs;intvertices,idx,source,sink,*head,*path,*visited;public:EdmondsKarp(intv,inte,ints,intt){verticesv;headnewint[v],pathnewint[v],visitednewint[v];arcsnewarc[e];sources,sinkt;idx0;memset(head,0xff,vertices*sizeof(int));}~EdmondsKarp(){delete[]head,path,visited,arcs;}intmaxFlow(){intflow0;while(true){memset(path,-1,vertices*sizeof(int));memset(visited,0,vertices*sizeof(int));queueintunvisited;unvisited.push(source);visited[source]1;while(!unvisited.empty()){intuunvisited.front();unvisited.pop();for(intxhead[u];x!-1;xarcs[x].next)if(!visited[arcs[x].v]arcs[x].residual0){unvisited.push(arcs[x].v);visited[arcs[x].v]1;path[arcs[x].v]x;}}if(!visited[sink])break;intdeltaINF;for(intxpath[sink];x!-1;xpath[arcs[x].u])deltamin(delta,arcs[x].residual);flowdelta;for(intxpath[sink];x!-1;xpath[arcs[x].u]){arcs[x].residual-delta;arcs[x^1].residualdelta;}}returnflow;}voidaddArc(intu,intv,intcapacity){arcs[idx](arc){u,v,capacity,capacity,head[u]};head[u]idx;arcs[idx](arc){v,u,capacity,0,head[v]};head[v]idx;}};intproblem,streets,avenues,banks;voidcreateGraph(EdmondsKarpek){// 上下左右四个顶点的坐标偏移量。intoffset[4][2]{{1,0},{0,-1},{-1,0},{0,1}};// 在源点和银行之间建立有向弧。for(intb1,x,y;bbanks;b){cinxy;ek.addArc(0,(x-1)*avenuesy,1);}// 在交叉路口之间和交叉路口与汇点间建立有向弧。intbasestreets*avenues;for(ints1;sstreets;s)for(inta1;aavenues;a){intindex(s-1)*avenuesa;// 将交叉路口拆分为前点和后点并建立有向弧。ek.addArc(index,baseindex,1);// 如果交叉路口不位于城镇的边界上则每个交叉路口的后点向上下左右四个// 交叉路口的前点建立有向弧否则在交叉路口的后点和汇点间建立有向弧。if(s1sstreetsa1aavenues){for(intf0;f4;f){intsssoffset[f][0],aaaoffset[f][1];if(ss1ssstreetsaa1aaavenues)ek.addArc(baseindex,(ss-1)*avenuesaa,1);}}elseek.addArc(baseindex,2*streets*avenues1,1);}}intmain(){cin.tie(0),cout.tie(0),ios::sync_with_stdio(false);cinproblem;for(intp1;pproblem;p){cinstreetsavenuesbanks;EdmondsKarpek(MAXV,MAXA,0,2*streets*avenues1);createGraph(ek);cout(ek.maxFlow()banks?possible:not possible)\n;}return0;}