\(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);
}