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