2h被逼学会网络流.png

Edmonds-Karp好像不是很难,唯一的难点好像是残量网络中用负权边转流……

参见#1    #2 (质量一般)

  • 板子
#include<cstdio>
#include<iostream>
#include<cstring>
#include<string>
#include<algorithm>
#include<cstdlib>
#include<iterator>
#include<cmath>
#include<queue>
using namespace std;

struct ed
{
    int pre,to,capx,flow;
}edge[200010]={0};
int nodenum,edgenum,fx,tx,wx,pointer[10010]={0},at=1,sx,ex;

queue<int> que;
int ag[10010]={0},ans=0,former[10010]={0};

inline void readx(int& x)
{
    x=0; int k=1; register char ch=0;
    while (ch<'0' || ch>'9') { ch=getchar(); if (ch=='-') k=-1; }
    while (ch>='0' && ch<='9') { x=x*10+ch-'0'; ch=getchar(); }
}

inline void Insert()
{
    at++;
    edge[at].pre=pointer[fx];
    edge[at].to=tx;
    edge[at].capx=wx;
    pointer[fx]=at;
    at++;
    edge[at].pre=pointer[tx];
    edge[at].to=fx;
    edge[at].capx=0;
    pointer[tx]=at;
}

inline void Max_Flow()
{
    int prex,cache1;
    while (1)
    {
        memset(ag,0,sizeof(ag));
        que.push(sx); ag[sx]=2*1e9;
        while (!que.empty())
        {
            cache1=que.front(); que.pop();
            prex=pointer[cache1];
            
            while (prex)
            {
                if ((!ag[edge[prex].to]) && edge[prex].capx)
                {
                    former[edge[prex].to]=prex;
                    ag[edge[prex].to]=min(ag[cache1],edge[prex].capx);					
                    que.push(edge[prex].to);
                }
                prex=edge[prex].pre;
            }
            if (ag[ex])
			{
				while (!que.empty()) que.pop();
				break;
			}
        }
        if (!ag[ex]) break;
        ans+=ag[ex];
        cache1=ex;
        while (former[cache1])
        {
            edge[former[cache1]].capx-=ag[ex];
            edge[former[cache1]^1].capx+=ag[ex];
            cache1=edge[former[cache1]^1].to;
        }
    }
}

int main()
{
    readx(nodenum); readx(edgenum); readx(sx); readx(ex);
    for (int i=1;i<=edgenum;i++)
    {
        readx(fx); readx(tx); readx(wx);
        Insert();
    }
    Max_Flow(); 
    cout<<ans<<endl;
    return 0;
}
#include<algorithm>
#include<cmath>
#include<cstring>
#include<string>
#include<cstdlib>
#include<iterator>
#include<iostream>
#include<cstdio>
#include<queue>
using namespace std;

struct ed
{
	int pre,to,capx;
}edge[400010]={0};
int nodenum,edgenum,at=1,pointer[100010]={0},sx,ex,fx,tx,cx;

queue<int> que;
int level[100010]={0},cache1; bool vis[100010]={0};
int ans=0;

inline void readx(int& x)
{
	x=0; int k=1; register char ch=0;
	while (ch<'0' || ch>'9') { ch=getchar(); if (ch=='-') k=-1; }
	while (ch>='0' && ch<='9') { x=x*10+ch-'0'; ch=getchar(); }
	x*=k;
}

inline void Insert()
{
	at++;
	edge[at].pre=pointer[fx];
	edge[at].to=tx;
	edge[at].capx=cx;
	pointer[fx]=at;
	at++;
	edge[at].pre=pointer[tx];
	edge[at].to=fx;
	edge[at].capx=0;
	pointer[tx]=at;
}

inline bool BFS()
{
	memset(vis,0,sizeof(vis));
	memset(level,0,sizeof(level));
	int prex=0; level[sx]=1; que.push(sx); vis[sx]=1;
	while (!que.empty())
	{
		cache1=que.front(); que.pop();
		prex=pointer[cache1];
		while (prex)
		{
			if (!vis[edge[prex].to] && edge[prex].capx)
			{
				level[edge[prex].to]=level[cache1]+1;
				que.push(edge[prex].to); vis[edge[prex].to]=true;
			}
			prex=edge[prex].pre;
		}
	}
	return vis[ex];
}

inline int DFS(int nownode,int minf)
{
	if ((!minf) || nownode==ex) return minf;
	int prex=pointer[nownode],needf=0,sumf=0;
	while (prex)
	{
		if (level[edge[prex].to]==level[nownode]+1)
			if (needf=DFS(edge[prex].to,min(minf,edge[prex].capx)))
			{
				edge[prex].capx-=needf; sumf+=needf;
				edge[prex^1].capx+=needf;
				minf-=needf;
				if (!minf) break;
			}
		prex=edge[prex].pre;
	}
	return sumf;
}

int main()
{
	readx(nodenum); readx(edgenum); readx(sx); readx(ex);
	for (int i=1;i<=edgenum;i++)
	{
		readx(fx); readx(tx); readx(cx);
		Insert();
	}
	
	while (BFS()) ans+=DFS(sx,2*1e9);
	
	printf("%d\n",ans);
	return 0;
}<span id="mce_marker" data-mce-type="bookmark" data-mce-fragment="1">​</span>

 

// luogu-judger-enable-o2
#include<cstdio>
#include<iostream>
#include<cstring>
#include<string>
#include<cmath>
#include<algorithm>
#include<cstdlib>
#include<iterator>
#include<queue>
using namespace std;

struct ed
{
    int pre,to,capx,cost;
}edge[100010]={0};
int nodenum,edgenum,at=1,pointer[100010]={0},fx,tx,wx,cx,sx,ex;

queue<int> que;
bool vis[100010]={0};
int dc[100010]={0},former[100010]={0},ag[100010]={0},prex,cache1;
int ansf=0,ansc=0;

inline void readx(int& x)
{
    x=0; int k=1; register char ch=0;
    while (ch<'0' || ch>'9') { ch=getchar(); if (ch=='-') k=-1; }
    while (ch>='0' && ch<='9') { x=x*10+ch-'0'; ch=getchar(); }
    x*=k;
}

inline void Insert()
{
    at++;
    edge[at].pre=pointer[fx];
    edge[at].to=tx;
    edge[at].capx=cx;
    edge[at].cost=wx;
    pointer[fx]=at;
    at++;
    edge[at].pre=pointer[tx];
    edge[at].to=fx;
    edge[at].cost=-wx;
    pointer[tx]=at;
}

inline bool MinCostMaxFlow()
{
    memset(ag,0,sizeof(ag));
    memset(vis,0,sizeof(vis));
    memset(former,0,sizeof(former));
    memset(dc,0x3f,sizeof(dc));
    dc[sx]=0; ag[sx]=2*1e9; vis[sx]=1; que.push(sx);
    while (!que.empty())
    {
        cache1=que.front(); que.pop();
        vis[cache1]=false; prex=pointer[cache1];
        while (prex)
        {
            if (edge[prex].capx && dc[edge[prex].to]>dc[cache1]+edge[prex].cost)
            {
                dc[edge[prex].to]=dc[cache1]+edge[prex].cost;
                ag[edge[prex].to]=min(ag[cache1],edge[prex].capx);
                former[edge[prex].to]=prex;
                if (!vis[edge[prex].to])
                {
                    vis[edge[prex].to]=true;
                    que.push(edge[prex].to);
                }
            }
            prex=edge[prex].pre;
        }
    }
    if (dc[ex]==dc[nodenum+2]) return false;
    
    ansf+=ag[ex]; ansc+=ag[ex]*dc[ex];
    cache1=former[ex];
    while (cache1)
    {
        edge[cache1].capx-=ag[ex];
        edge[cache1^1].capx+=ag[ex];
        cache1=former[edge[cache1^1].to];
    }
    return true;
}

int main()
{
    readx(nodenum); readx(edgenum); readx(sx); readx(ex);
    for (int i=1;i<=edgenum;i++)
    {
        readx(fx); readx(tx); readx(cx); readx(wx);
        Insert();
    }
    
    while (MinCostMaxFlow()) ;
    
    printf("%d %d\n",ansf,ansc);
    return 0;
}

 


			
分类: 网络流

发表评论

电子邮件地址不会被公开。 必填项已用*标注

This site uses Akismet to reduce spam. Learn how your comment data is processed.