首页 > 代码库 > Uva 563 网络流
Uva 563 网络流
题目链接:点击打开链接
题意:给定s*a的方格点,有b个坐标是有且仅有一个人的。
每个点只能被经过一次
能不能让所有人都移动到矩阵边缘。
拆点一下,建图还是挺明显的。。
太卡了提交半天没结果,贴一下代码改天再搞好了。。
//好吧1A了。。
#include<stdio.h> #include<string.h> #include<iostream> #include<algorithm> #include<vector> using namespace std; #define ll int const int MAXN = 100010;//点数的最大值 const int MAXM = 400010;//边数的最大值 const int INF = 0x3f3f3f3f; struct Edge { int to,next,cap,flow; }edge[MAXM];//注意是MAXM int tol; int head[MAXN]; int gap[MAXN],dep[MAXN],cur[MAXN]; void add(int u,int v,int w,int rw = 0) { edge[tol].to = v; edge[tol].cap = w; edge[tol].flow = 0; edge[tol].next = head[u]; head[u] = tol++; edge[tol].to = u; edge[tol].cap = rw; edge[tol].flow = 0; edge[tol].next = head[v]; head[v] = tol++; } int Q[MAXN]; void BFS(int start,int end) { memset(dep,-1,sizeof(dep)); memset(gap,0,sizeof(gap)); gap[0] = 1; int front = 0, rear = 0; dep[end] = 0; Q[rear++] = end; while(front != rear) { int u = Q[front++]; for(int i = head[u]; i != -1; i = edge[i].next) { int v = edge[i].to; if(dep[v] != -1)continue; Q[rear++] = v; dep[v] = dep[u] + 1; gap[dep[v]]++; } } } int S[MAXN]; int sap(int start,int end,int N) { BFS(start,end); memcpy(cur,head,sizeof(head)); int top = 0; int u = start; int ans = 0; while(dep[start] < N) { if(u == end) { int Min = INF; int inser; for(int i = 0;i < top;i++) if(Min > edge[S[i]].cap - edge[S[i]].flow) { Min = edge[S[i]].cap - edge[S[i]].flow; inser = i; } for(int i = 0;i < top;i++) { edge[S[i]].flow += Min; edge[S[i]^1].flow -= Min; } ans += Min; top = inser; u = edge[S[top]^1].to; continue; } bool flag = false; int v; for(int i = cur[u]; i != -1; i = edge[i].next) { v = edge[i].to; if(edge[i].cap - edge[i].flow && dep[v]+1 == dep[u]) { flag = true; cur[u] = i; break; } } if(flag) { S[top++] = cur[u]; u = v; continue; } int Min = N; for(int i = head[u]; i != -1; i = edge[i].next) if(edge[i].cap - edge[i].flow && dep[edge[i].to] < Min) { Min = dep[edge[i].to]; cur[u] = i; } gap[dep[u]]--; if(!gap[dep[u]])return ans; dep[u] = Min + 1; gap[dep[u]]++; if(u != start)u = edge[S[--top]^1].to; } return ans; } void init(){ tol = 0; memset(head,-1,sizeof(head)); } int n,m,b; int Hash(int x,int y){return (x-1)*m+y;} int Hash2(int x,int y){return (x-1)*m+y + n*m;} bool inmap(int x,int y){return 1<=x&&x<=n&&1<=y&&y<=m;} int step[4][2] = {0,1,0,-1,1,0,-1,0}; int main(){ int T, u, v, i, j; scanf("%d",&T); while(T--){ init(); scanf("%d %d %d",&n,&m,&b); int from = 0, to = Hash2(n,m)+1; for(i = 0; i < b; i++) { int px, py; scanf("%d %d",&px,&py); add(from, Hash(px,py), 1); } for(i = 1; i <= n; i++) { for(j = 1; j <= m; j++) { add(Hash(i,j), Hash2(i,j), 1); for(int k = 0; k < 4; k++) { int nowx = i+step[k][0], nowy = j+step[k][1]; if(!inmap(nowx,nowy))continue; add(Hash2(i,j), Hash(nowx,nowy), INF); } } } for(i = 1; i <= n; i++) { add(Hash2(i,1), to, INF); add(Hash2(i,m), to, INF); } for(i = 1; i <= m; i++) { add(Hash2(1,i), to, INF); add(Hash2(n,i), to, INF); } b == sap(from, to, to+1) ? puts("possible"):puts("not possible"); } return 0; }
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。