锐客网

  1. 首页 > it技术 > >

uva 10779 Collectors Problem(最大流,好题)

题目链接
训练指南上的一道题，P370，很好的一个建图。
【uva 10779 Collectors Problem(最大流,好题)】


#include #include #include #include using namespace std; const int MAXN=45; const int MAXM=MAXN*MAXN; const int INF=0x3f3f3f3f; struct Node { int from,to,next; int cap; }edge[MAXM]; int tol; int dep[MAXN]; //dep为点的层次 int head[MAXN]; void init() { tol=0; memset(head,-1,sizeof(head)); } void addedge(int u,int v,int w)//第一条边下标必须为偶数 { edge[tol].from=u; edge[tol].to=v; edge[tol].cap=w; edge[tol].next=head[u]; head[u]=tol++; edge[tol].from=v; edge[tol].to=u; edge[tol].cap=0; edge[tol].next=head[v]; head[v]=tol++; } int BFS(int start,int end) { int que[MAXN]; int front,rear; front=rear=0; memset(dep,-1,sizeof(dep)); que[rear++]=start; dep[start]=0; while(front!=rear) { int u=que[front++]; if(front==MAXN)front=0; for(int i=head[u]; i!=-1; i=edge[i].next) { int v=edge[i].to; if(edge[i].cap>0&&dep[v]==-1) { dep[v]=dep[u]+1; que[rear++]=v; if(rear>=MAXN)rear=0; if(v==end)return 1; } } } return 0; } int dinic(int start,int end) { int res=0; int top; int stack[MAXN]; //stack为栈，存储当前增广路 int cur[MAXN]; //存储当前点的后继 while(BFS(start,end)) { memcpy(cur,head,sizeof(head)); int u=start; top=0; while(1) { if(u==end) { int min=INF; int loc; for(int i=0; iedge[stack[i]].cap) { min=edge[stack[i]].cap; loc=i; } for(int i=0; i



    推荐阅读


    上一篇：django|uwsgi+Django 部署 前后端不分离web项目

    下一篇：AS|AS 3.0 电波