淺談費用流

• 2022 年 1 月 6 日
• 筆記

\(SAP\)

\(\mathcal{No.1} 方法及證明\)

\(SSP演算法是一個貪心的演算法。它的思路是每次尋找單位費用最小的增廣路進行增廣，直到圖上不存在增廣路為止。\)

\(如果圖上存在單位費用為負的圈，SSP 演算法正確無法求出該網路的最小費用最大流。此時需要先使用消圈演算法消去圖上的負圈。\)

\(同dinic一樣，這裡的增廣路的長度是單調不遞減的\)

\(這樣找能夠保證最大流，但需證明一定是最小費用\)

\(引理:當流量為i時，且圖中不存在負環，那麼此時是流量為i時最小費用\)

\(考慮對於流量為i的f_i及其i+1的f_{i+1}\)

\(假設f_i為最小費用並且f_{i+1}為f_i用最短路增廣出的流\)

\(假設存在f_{i+1}’為f_i增廣出的流比f_i更小\)

\(\therefore f_{i+1}’的增廣路徑小於f_{i+1}\)

\(\therefore f_{i+1}’的增廣路徑中有負環，這與其矛盾\)

\(回到其最開始的證明,即最短路增廣的正確性\)

\(設f_i為第i次增廣的流\)

\(假設存在f_i’,使得|f’_i|=|f_i|且f’_i的花費小於f_i的花費\)

\(由於|f_{i-1}|<|f’_{i}|,因此一定存在增廣路於f_{i-1}到f’_{i}\)

\(又由於f’_i的花費小於f_i的花費，f_i是最短路增廣\)

\(所以f’_i的增廣路徑存在負環，於引理矛盾，因此假設不成立\)

\(\mathcal{No.2} 例題\)

P4134 [BJOI2012]連連看

\(給每一個滿足條件的x,y連邊，可以發現在1000以內是一個二分圖，跑最大費用流即可\)

#include <bits/stdc++.h>
using namespace std;
const int INF = 0x3f3f3f3f;
const int MAXN = 6005;
const int MAXM = 50005;
int n, m;
int x, y, z, c;
struct Edge {
    int to, nex;
    int val;
    int cost;
} edge[MAXM * 2];
int cnt = 1;
int head[MAXN];
void Add(int u, int v, int w, int cost) {
    edge[++cnt].to = v;
    edge[cnt].nex = head[u];
    edge[cnt].val = w;
    edge[cnt].cost = -cost;
    head[u] = cnt;
}

int dis[MAXN];
int vis[MAXN];
int arc[MAXN];
int s, t;
int Energy[MAXN];
bool spfa() {
    memset(dis, 0x3f, sizeof(dis));
    memset(vis, 0, sizeof(vis));
    queue<int>q;

    q.push(s);
    dis[s] = 0;
    vis[s] = 1;

    while (q.size()) {
        int temp = q.front();
        q.pop();
        vis[temp] = 0;
        arc[temp] = head[temp];

        for (int i = head[temp]; i; i = edge[i].nex) {
            int v = edge[i].to;
            int w = edge[i].cost;

            if (!edge[i].val) {
                continue;
            }

            if (dis[v] > dis[temp] + w) {
                dis[v] = dis[temp] + w;

                if (!vis[v]) {
                    vis[v] = 1;
                    q.push(v);
                }
            }
        }
    }

    memset(vis, 0, sizeof(vis));

    if (dis[t] == 0x3f3f3f3f) {
        return 0;
    }

    return 1;

}
int mincost = 0;
int maxflow = 0;
int dfs(int x, int flow) {
    if (x == t || flow == 0) {
        return flow;
    }

    int used = 0;
    vis[x] = 1;

    for (int i = arc[x]; i; i = edge[i].nex) {

        int v = edge[i].to;
        int w = edge[i].cost;
        if (vis[v]) {
            continue;
        }

        if (!edge[i].val) {
            continue;
        }

        if (dis[x] + w == dis[v]) {
            arc[x] = i;
            int nowu = dfs(v, min(flow - used, edge[i].val));
            used += nowu;

            edge[i].val -= nowu;
            edge[i ^ 1].val += nowu;
            mincost += nowu * w;

            if (used == flow) {
                break;
            }
        }
    }

    vis[x] = 0;
    return used;
}
struct node{
	int u,val;
	bool operator<(const node x)const{
		return val>x.val;
	}
};
bool dijkstra()
{
	
	for(int i=0;i<=n+50;i++)
	{
		dis[i]=0x3f3f3f3f;
		vis[i]=0;
		 
	}
	dis[s]=0;
	arc[s]=head[s];
	priority_queue<node>q;
	node gsg;
	gsg.u=s;
	gsg.val=0;
	q.push(gsg);
	while(q.size())
	{
		node temp=q.top();
		q.pop();
		if(vis[temp.u])
		{
			continue;
		}
		vis[temp.u]=1;
		arc[temp.u]=head[temp.u];
		for(int i=head[temp.u];i;i=edge[i].nex)
		{
			int v=edge[i].to;
			int w=Energy[temp.u]-Energy[v]+edge[i].cost;//保證無負權 
			if(!edge[i].val)
			{
				continue;
			}
			if(dis[v]>dis[temp.u]+w)
			{
				dis[v]=dis[temp.u]+w;
				node gaf;
				gaf.val=dis[v];
				gaf.u=v;
				q.push(gaf);
			}
		}
	}
	for(int i = 0; i <= n+50; i++)
	{
 		dis[i]=dis[i]-Energy[s]+Energy[i];//勢能函數的更新要累加當前的 
    }
    for(int i = 0; i <= n+50; i++)
    {
    	Energy[i] = dis[i];
	}
        

	memset(vis,0,sizeof(vis));
	if(dis[t]>=0x3f3f3f3f)
	{
		return 0;
	}
	return 1;
 } 
pair<int, int>dinic() {
	mincost=0;
	maxflow=0;
    if(!spfa())
    {
    	return make_pair(maxflow,mincost);
	}
	for(int i=0;i<=n+50;i++)
	{
		Energy[i]=dis[i];
	}//這裡清空要注意範圍 
	while(dijkstra())
	{
	//	printf("fiuck");
		maxflow+=dfs(s,INF);
		
	}
	return make_pair(maxflow,mincost);
	
}
int clor[MAXN];
vector<int>g[MAXN];
bool is2(int x)
{
	if(int(sqrt(x))==sqrt(x))
	{
		return 1;
	}
	return 0;
 } 
 int gcd(int a,int b){
 	if(!b)
 	{
 		return a;
	 }
	 return gcd(b,a%b);
 }
 void Dfs(int x,int clo)
 {
 	if(clor[x])
 	{
 		return;
	 }
	 clor[x]=clo;
	 for(int i=0;i<g[x].size();i++)
	 {
	 	int v=g[x][i];
	 	Dfs(v,clo==1?2:1);
	 }
 }
int main() {
	scanf("%d %d",&m,&n);
	for(int i=m;i<=n;i++)
	{
		for(int j=m+1;j<=n;j++)
		{
			if(is2(j*j-i*i))
			{
				//printf("%d %d\n",i,j);
				if(gcd(i,sqrt(j*j-i*i))==1)
				{
					g[i].push_back(j);
					g[j].push_back(i); 
					
				}
			}
		}	
	}    
	for(int i=m;i<=n;i++)
	{
		if(!clor[i])
		{
			Dfs(i,1);
		}
	}
	for(int i=m;i<=n;i++)
	{
		if(clor[i]==1)
		{
			Add(0,i-m+1,1,0);
			Add(i-m+1,0,0,0);
			for(int j=0;j<g[i].size();j++)
			{
				int v=g[i][j];
				Add(i-m+1,v-m+1,1,i+v);
				Add(v-m+1,i-m+1,0,-(i+v));
			}
		}
		else
		{
			Add(i-m+1,n-m+2,1,0);
			Add(n-m+2,i-m+1,0,0);
		}
	}
	s=0;
	t=n-m+2;
	pair<int,int>pi=dinic();
	printf("%d %d",pi.first,pi.second*-1);
}

#include <bits/stdc++.h>
using namespace std;
const int INF = 0x3f3f3f3f;
const int MAXN = 4005;
const int MAXM = 50005;
int n, m;
int x, y, z, c;
struct Edge {
    int to, nex;
    int val;
    int cost;
} edge[MAXM * 2];
int cnt = 1;
int head[MAXN];
void Add(int u, int v, int w, int cost) {
    edge[++cnt].to = v;
    edge[cnt].nex = head[u];
    edge[cnt].val = w;
    edge[cnt].cost = cost;
    head[u] = cnt;
}

int dis[MAXN];
int vis[MAXN];
int arc[MAXN];
int s, t;

bool spfa() {
    for(int i=s;i<=t;i++)
    {
    	dis[i]=-0x3f3f3f3f;
	}
    memset(vis, 0, sizeof(vis));
    queue<int>q;

    q.push(s);
    dis[s] = 0;
    vis[s] = 1;

    while (q.size()) {
        int temp = q.front();
        q.pop();
        vis[temp] = 0;
        arc[temp] = head[temp];

        for (int i = head[temp]; i; i = edge[i].nex) {
            int v = edge[i].to;
            int w = edge[i].cost;

            if (!edge[i].val) {
                continue;
            }

            if (dis[v] < dis[temp] + w) {
                dis[v] = dis[temp] + w;

                if (!vis[v]) {
                    vis[v] = 1;
                    q.push(v);
                }
            }
        }
    }

    memset(vis, 0, sizeof(vis));

    if (dis[t] == -0x3f3f3f3f) {
        return 0;
    }

    return 1;

}
int mincost = 0;
int maxflow = 0;
int dfs(int x, int flow) {
    if (x == t || flow == 0) {
        return flow;
    }

    int used = 0;
    vis[x] = 1;

    for (int i = arc[x]; i; i = edge[i].nex) {

        int v = edge[i].to;
        int w = edge[i].cost;

        if (vis[v]) {
            continue;
        }

        if (!edge[i].val) {
            continue;
        }

        if (dis[x] + w == dis[v]) {
            arc[x] = i;
            int nowu = dfs(v, min(flow - used, edge[i].val));
            used += nowu;

            edge[i].val -= nowu;
            edge[i ^ 1].val += nowu;
            mincost += nowu * w;

            if (used == flow) {
                break;
            }
        }
    }

    vis[x] = 0;
    return used;
}
pair<int, int>dinic() {
    maxflow = 0;
    mincost = 0;
    int flow = 0;

    while (spfa()) {
        maxflow += dfs(s, INF);
    }

    return make_pair(maxflow, mincost);
}
int clor[MAXN];
vector<int>g[MAXN];
bool is2(int x)
{
	if(int(sqrt(x))==sqrt(x))
	{
		return 1;
	}
	return 0;
 } 
 int gcd(int a,int b){
 	if(!b)
 	{
 		return a;
	 }
	 return gcd(b,a%b);
 }
 void Dfs(int x,int clo)
 {
 	if(clor[x])
 	{
 		return;
	 }
	 clor[x]=clo;
	 for(int i=0;i<g[x].size();i++)
	 {
	 	int v=g[x][i];
	 	Dfs(v,clo==1?2:1);
	 }
 }
int main() {
	scanf("%d %d",&m,&n);
	for(int i=m;i<=n;i++)
	{
		for(int j=m+1;j<=n;j++)
		{
			if(is2(j*j-i*i))
			{
				//printf("%d %d\n",i,j);
				if(gcd(i,sqrt(j*j-i*i))==1)
				{
					g[i].push_back(j);
					g[j].push_back(i); 
					
				}
			}
		}	
	}    
	for(int i=m;i<=n;i++)
	{
		if(!clor[i])
		{
			Dfs(i,1);
		}
	}
	for(int i=m;i<=n;i++)
	{
		if(clor[i]==1)
		{
			Add(0,i-m+1,1,0);
			Add(i-m+1,0,0,0);
			for(int j=0;j<g[i].size();j++)
			{
				int v=g[i][j];
				Add(i-m+1,v-m+1,1,i+v);
				Add(v-m+1,i-m+1,0,-(i+v));
			}
		}
		else
		{
			Add(i-m+1,n-m+2,1,0);
			Add(n-m+2,i-m+1,0,0);
		}
	}
	s=0;
	t=n-m+2;
	pair<int,int>pi=dinic();
	printf("%d %d",pi.first,pi.second);
}