餐巾计划问题

将每天的早晚分开，分成两个点，然后建图

如果要让最大流等于每天用到的餐巾数量之和，那么一定要满足每天都要向汇点连一条容量为当天餐巾数量的边。

如何体现餐巾的重复利用呢？答案是从源点向每天晚上连容量为当天餐巾数量的边。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int MAXN=4e3+5;
const int MAXM=2e4+5;
const int INF=1e9;
int N;
int cp,dm,cf,dn,cs,lim[MAXN];

int head[MAXN], cnt = 1;  // 这里特意把存图也贴出来，记住额外存一个参数c（费用）
struct Edge
{
    int to, w, c, next;
} edges[MAXM * 2];
inline void add(int from, int to, int w, int c)
{
    edges[++cnt].to = to;
    edges[cnt].w = w;
    edges[cnt].c = c;
    edges[cnt].next = head[from];
    head[from] = cnt;

	edges[++cnt].to = from;
	edges[cnt].w = 0;
	edges[cnt].c = -c;
	edges[cnt].next = head[to];
	head[to] = cnt;
	
}
int n, m, s, t, last[MAXN], flow[MAXN], inq[MAXN], dis[MAXN];
queue<int> Q;
bool SPFA()
{
    while (!Q.empty())
        Q.pop();
    memset(last, -1, sizeof(last));
    memset(inq, 0, sizeof(inq));
    memset(dis, 127, sizeof(dis));
    flow[s] = INF;
    dis[s] = 0;
    Q.push(s);
    while (!Q.empty())
    {
        int p = Q.front();
        Q.pop();
        inq[p] = 0;
        for (int eg = head[p]; eg != 0; eg = edges[eg].next)
        {
            int to = edges[eg].to, vol = edges[eg].w;
            if (vol > 0 && dis[to] > dis[p] + edges[eg].c) // 容量大于0才增广
            {
                last[to] = eg; // 记录上一条边
                flow[to] = min(flow[p], vol); // 更新下一个点的流量
                dis[to] = dis[p] + edges[eg].c; // 注意这里是c不是w
                if (!inq[to])
                {
                    Q.push(to);
                    inq[to] = 1;
                }
            }
        }
    }
    return last[t] != -1;
}
ll maxflow, mincost;
inline void MCMF() // 这里要求两个值，直接改成给全局变量赋值了，传pair也可以吧
{
	int tot=0;
    while (SPFA())
    {
        maxflow += flow[t];
        mincost += 1ll * dis[t] * flow[t];
        for (int i = t; i != s; i = edges[last[i] ^ 1].to)
        {
            edges[last[i]].w -= flow[t];
            edges[last[i] ^ 1].w += flow[t];
        }
    }
}
void init(){
	n=N*2+2;
	for(int i=1;i<=N;i++){
		add(i,n-1,lim[i],0);
		add(0,i,INF,cp);
		add(0,i+N,lim[i],0);
		if(i!=N)add(i+N,i+N+1,INF,0);
		if(i+dm<=N)add(i+N,i+dm,INF,cf);
		if(i+dn<=N)add(i+N,i+dn,INF,cs);
	}
	s=0,t=n-1;

}
int main(){
	ios::sync_with_stdio(0);
	cin.tie(0);
	cin>>N;
	for(int i=1;i<=N;i++)cin>>lim[i];
	cin>>cp>>dm>>cf>>dn>>cs;
	init();
	MCMF();
	cout<<mincost<<'\n';
	return 0;
}

试题库问题

水题

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int MAXN=1e3+100;
const int MAXM=5e4+5;
const int INF=1e9;
int N,k,lim[MAXN];
vector<int>vec[MAXN];
vector<int>ans[MAXN];
int n, m, s, t;

struct Edge{
    ll to, next, weight;
};
Edge edges[MAXM]; 
int edge_cnt = 1, head[MAXN], cur[MAXN];

void add(int x,int y,int w){
    edges[++edge_cnt].next = head[x];
    edges[edge_cnt].to = y;
    edges[edge_cnt].weight = w;
    head[x] = edge_cnt ;

    edges[++edge_cnt].next = head[y];
    edges[edge_cnt].to = x;
    edges[edge_cnt].weight = 0;
    head[y] = edge_cnt ;
}

int level[MAXN];
bool bfs(){
    memset(level, 0, sizeof(level));
    memcpy(cur, head, sizeof(head));
    queue<int> q;
    q.push(s);
    level[s] = 1;
    while (!q.empty()){
        int u = q.front();
        q.pop();
        for (int i = head[u]; i != 0; i = edges[i].next){
            ll v = edges[i].to, flow = edges[i].weight;
            if (flow > 0 && level[v] == 0){
                level[v] = level[u] + 1;
                q.push(v);
            }
        }   
    }
    return (level[t] != 0);
}

int dfs(int p = s, int cur_flow = INF){
    if (p == t) return cur_flow;
    ll ret = 0;
    for (int i = cur[p]; i != 0; i = edges[i].next){
        cur[p] = i;
        ll v = edges[i].to, vol = edges[i].weight;
        if (level[v] == level[p] + 1 && vol > 0){
            int f = dfs(v, min(cur_flow - ret, vol));
            edges[i].weight -= f;
            edges[i^1].weight += f;
            ret += f;
            if (ret == cur_flow) return ret;
        }
    }
    return ret;
}

ll dinic(){
    ll max_flow = 0;
    while (bfs()){
        max_flow += dfs();
    }
    return max_flow;
}
void init(){
	n=N+k+2;
	s=0,t=n-1;
	for(int i=1;i<=N;i++){
		add(s,i,1);
		for(auto j:vec[i]){
			add(i,j+N,1);
		}
	}
	for(int i=1;i<=k;i++){
		add(i+N,t,lim[i]);
	}
}
void print(){
	for(int i=1;i<=k;i++){
		for(int j=head[i+N];j;j=edges[j].next){
			int v=edges[j].to,w=edges[j].weight;
			if(w&&v<=N)ans[i].push_back(v);
			if(v==t&&w){
				puts("No Solution!");
				return;
			}
		}
	}
	
	for(int i=1;i<=k;i++){
		cout<<i<<":";
		for(auto x:ans[i])cout<<" "<<x;
		cout<<"\n";
	}
}
int main(){
	// ios::sync_with_stdio(0);
	// cin.tie(0);
	cin>>k>>N;
	for(int i=1;i<=k;i++)scanf("%d",&lim[i]);
	for(int i=1;i<=N;i++){
		int sz;scanf("%d",&sz);
		for(int j=1;j<=sz;j++){
			int x;scanf("%d",&x);
			vec[i].push_back(x);
		}
	}

	init();
	dinic();
	print();
	return 0;
}

运输问题

水题

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int MAXN=2e2+5;
const int MAXM=3e4+5;
const int INF=1e9;
int N,M;
int a[MAXN],b[MAXN],c[MAXN][MAXN];

int head[MAXN], cnt = 1;  // 这里特意把存图也贴出来，记住额外存一个参数c（费用）
struct Edge
{
    int to, w, c, next;
} edges[MAXM * 2];
inline void add(int from, int to, int w, int c)
{
    edges[++cnt].to = to;
    edges[cnt].w = w;
    edges[cnt].c = c;
    edges[cnt].next = head[from];
    head[from] = cnt;

	edges[++cnt].to = from;
	edges[cnt].w = 0;
	edges[cnt].c = -c;
	edges[cnt].next = head[to];
	head[to] = cnt;
	
}
int n, m, s, t, last[MAXN], flow[MAXN], inq[MAXN], dis[MAXN];
queue<int> Q;
bool SPFA()
{
    while (!Q.empty())
        Q.pop();
    memset(last, -1, sizeof(last));
    memset(inq, 0, sizeof(inq));
    memset(dis, 127, sizeof(dis));
    flow[s] = INF;
    dis[s] = 0;
    Q.push(s);
    while (!Q.empty())
    {
        int p = Q.front();
        Q.pop();
        inq[p] = 0;
        for (int eg = head[p]; eg != 0; eg = edges[eg].next)
        {
            int to = edges[eg].to, vol = edges[eg].w;
            if (vol > 0 && dis[to] > dis[p] + edges[eg].c) // 容量大于0才增广
            {
                last[to] = eg; // 记录上一条边
                flow[to] = min(flow[p], vol); // 更新下一个点的流量
                dis[to] = dis[p] + edges[eg].c; // 注意这里是c不是w
                if (!inq[to])
                {
                    Q.push(to);
                    inq[to] = 1;
                }
            }
        }
    }
    return last[t] != -1;
}
ll maxflow, mincost;
inline void MCMF() // 这里要求两个值，直接改成给全局变量赋值了，传pair也可以吧
{
	maxflow=mincost=0;
    while (SPFA())
    {
        maxflow += flow[t];
        mincost += 1ll * dis[t] * flow[t];
        for (int i = t; i != s; i = edges[last[i] ^ 1].to)
        {
            edges[last[i]].w -= flow[t];
            edges[last[i] ^ 1].w += flow[t];
        }
    }
}
void init(){
	n=N+M+2;
	s=0,t=n-1;
	for(int i=1;i<=M;i++){
		add(0,i,a[i],0);
		for(int j=1;j<=N;j++){
			add(i,j+M,a[i],c[i][j]);
		}
	}
	for(int i=1;i<=N;i++){
		add(i+M,t,b[i],0);
	}

}
int main(){
	ios::sync_with_stdio(0);
	cin.tie(0);
	cin>>M>>N;
	for(int i=1;i<=M;i++)cin>>a[i];
	for(int i=1;i<=N;i++)cin>>b[i];
	for(int i=1;i<=M;i++){
		for(int j=1;j<=N;j++)cin>>c[i][j];
	}
	init();
	MCMF();
	cout<<mincost<<'\n';

	cnt=1;
	memset(head,0,sizeof(head));
	init();
	for(int i=1;i<MAXM;i++)edges[i].c*=-1;
	MCMF();
	cout<<-mincost<<'\n';
	return 0;
}

圆桌问题

还是个水题…

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int MAXN=1e3+5;
const int MAXM=1e5+5;
const int INF=1e9;
vector<int>vec[MAXN];
vector<int>ans[MAXN];
int M,N,r[MAXN],c[MAXN];
int n, m, s, t;
struct Edge{
    ll to, next, weight;
};
Edge edges[MAXM]; 
int edge_cnt = 1, head[MAXN], cur[MAXN];

void add(int x,int y,int w){
    edges[++edge_cnt].next = head[x];
    edges[edge_cnt].to = y;
    edges[edge_cnt].weight = w;
    head[x] = edge_cnt ;

    edges[++edge_cnt].next = head[y];
    edges[edge_cnt].to = x;
    edges[edge_cnt].weight = 0;
    head[y] = edge_cnt ;
}

int level[MAXN];
bool bfs(){
    memset(level, 0, sizeof(level));
    memcpy(cur, head, sizeof(head));
    queue<int> q;
    q.push(s);
    level[s] = 1;
    while (!q.empty()){
        int u = q.front();
        q.pop();
        for (int i = head[u]; i != 0; i = edges[i].next){
            ll v = edges[i].to, flow = edges[i].weight;
            if (flow > 0 && level[v] == 0){
                level[v] = level[u] + 1;
                q.push(v);
            }
        }   
    }
    return (level[t] != 0);
}

int dfs(int p = s, int cur_flow = INF){
    if (p == t) return cur_flow;
    ll ret = 0;
    for (int i = cur[p]; i != 0; i = edges[i].next){
        cur[p] = i;
        ll v = edges[i].to, vol = edges[i].weight;
        if (level[v] == level[p] + 1 && vol > 0){
            int f = dfs(v, min(cur_flow - ret, vol));
            edges[i].weight -= f;
            edges[i^1].weight += f;
            ret += f;
            if (ret == cur_flow) return ret;
        }
    }
    return ret;
}

ll dinic(){
    ll max_flow = 0;
    while (bfs()){
        max_flow += dfs();
    }
    return max_flow;
}
void init(){
	n=N+M+2;
	s=0,t=n-1;
	for(int i=1;i<=M;i++){
		add(s,i,r[i]);
		for(int j=1;j<=N;j++){
			add(i,j+M,1);
		}
	}
	for(int i=1;i<=N;i++){
		add(i+M,t,c[i]);
	}
}
void print(){
	for(int i=1;i<=M;i++){
		for(int j=head[i];j;j=edges[j].next){
			int v=edges[j].to,w=edges[j].weight;
			if(v==s&&w!=r[i]){
				cout<<"0"<<'\n';
				return;
			}
			if(v>M&&!w){
				ans[i].push_back(v-M);
			}
		}
	}
	cout<<"1"<<'\n';	
	for(int i=1;i<=M;i++){
		for(auto x:ans[i])cout<<x<<" ";
		cout<<"\n";
	}
}
int main(){
	ios::sync_with_stdio(0);
	cin.tie(0);
	cin>>M>>N;
	for(int i=1;i<=M;i++)cin>>r[i];
	for(int i=1;i<=N;i++)cin>>c[i];
	init();
	dinic();
	print();
	return 0;
}

骑士共存问题

网络流的优势在于，可以实现一种决策，使得每次操作都不会使结果变劣。所以拿到这个题我的第一反应是构建一种模型，当放置一个棋子之后，与其互斥的位置就自动被屏蔽掉，奈何本人太菜，此路不通。

于是换一种思维方式，利用最大流最小割求解。

通过观察可以发现，如果将棋盘使用国际象棋的方式黑白染色，那么互斥的位置颜色一定是不同的。于是可以从黑色的点向着互斥的白点连边。这样求得的最大流,即为必须去除的棋子。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int MAXN=1e5+100;
const int MAXM=1e6+5;
const int INF=1e9;
int N,M,vis[205][205];
int n, m, s, t;

struct Edge{
    ll to, next, weight;
};
Edge edges[MAXM]; 
int edge_cnt = 1, head[MAXN], cur[MAXN];
int dx[8]={2,2,1,-1,-2,-2,-1,1};
int dy[8]={-1,1,2,2,1,-1,-2,-2};
void add(int x,int y,int w){
    edges[++edge_cnt].next = head[x];
    edges[edge_cnt].to = y;
    edges[edge_cnt].weight = w;
    head[x] = edge_cnt ;

    edges[++edge_cnt].next = head[y];
    edges[edge_cnt].to = x;
    edges[edge_cnt].weight = 0;
    head[y] = edge_cnt ;
}

int level[MAXN];
bool bfs(){
    memset(level, 0, sizeof(level));
    memcpy(cur, head, sizeof(head));
    queue<int> q;
    q.push(s);
    level[s] = 1;
    while (!q.empty()){
        int u = q.front();
        q.pop();
        for (int i = head[u]; i != 0; i = edges[i].next){
            ll v = edges[i].to, flow = edges[i].weight;
            if (flow > 0 && level[v] == 0){
                level[v] = level[u] + 1;
                q.push(v);
            }
        }   
    }
    return (level[t] != 0);
}

int dfs(int p = s, int cur_flow = INF){
    if (p == t) return cur_flow;
    ll ret = 0;
    for (int i = cur[p]; i != 0; i = edges[i].next){
        cur[p] = i;
        ll v = edges[i].to, vol = edges[i].weight;
        if (level[v] == level[p] + 1 && vol > 0){
            int f = dfs(v, min(cur_flow - ret, vol));
            edges[i].weight -= f;
            edges[i^1].weight += f;
            ret += f;
            if (ret == cur_flow) return ret;
        }
    }
    return ret;
}

ll dinic(){
    ll max_flow = 0;
    while (bfs()){
        max_flow += dfs();
    }
    return max_flow;
}
bool check(int x){
	if(x>N||x<1)return false;
	return true;
}
void init(){
	n=N*N*2+2;
	s=0,t=n-1;
	for(int i=1;i<=N;i++){
		for(int j=1;j<=N;j++){
			if(vis[i][j])continue;
			int cur=(i-1)*N+j;
			if((i+j)%2!=0)add(cur+N*N,t,1);
			else {
				add(s,cur,1);
				for(int k=0;k<8;k++){
					int nx=dx[k]+i;
					int ny=dy[k]+j;
					if(check(nx)&&check(ny)&&!vis[nx][ny])
						add(cur,(nx-1)*N+ny+N*N,INF);
				}
			}
		}
	}
}

int main(){
	ios::sync_with_stdio(0);
	cin.tie(0);
	cin>>N>>M;
	for(int i=1;i<=M;i++){
		int x,y;
		cin>>x>>y;
		vis[x][y]=1;
	}
	init();
	cout<<N*N-dinic()-M;
	return 0;
}

航空路线问题

终于遇到一个比较好玩的题了指de了一下午bug

问题中说需要找到两条路径，并且使得点越多越好。所以很自然地想到把点数看成value。

难点在于，如何把“找到两条路径”化为最大流模型。

考虑拆点，把每个点拆成一个入点和出点两个点，两个点之间连一条容量为1，费用为1的边（如果是1和n点则容量为2）

对于原图中的边(u,v)，则从u的出点向着v的出点连容量为2的边即可（容量设置为2是因为有可能有1到n的直达边，这条边是很有可能被走两次的，虽然其他边最多被走一次，但是如果都这样设置容量为2可以方便代码实现，而且不会影响正确性）。

然后再从源点向1的入点连边，从n的出点向汇点连边。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int MAXN=3e2+5;
const int MAXM=2e5+5;
const int INF=1e9;
int N,M,idx;
string ct[MAXN];
map<string,int>mp;

int head[MAXN], cnt = 1;  // 这里特意把存图也贴出来，记住额外存一个参数c（费用）
struct Edge
{
    int to, w, c, next;
} edges[MAXM * 2];
inline void add(int from, int to, int w, int c)
{
    edges[++cnt].to = to;
    edges[cnt].w = w;
    edges[cnt].c = c;
    edges[cnt].next = head[from];
    head[from] = cnt;

	edges[++cnt].to = from;
	edges[cnt].w = 0;
	edges[cnt].c = -c;
	edges[cnt].next = head[to];
	head[to] = cnt;
	
}
int n, m, s, t, last[MAXN], flow[MAXN], inq[MAXN], dis[MAXN];
queue<int> Q;
bool SPFA()
{
    while (!Q.empty())
        Q.pop();
    memset(last, -1, sizeof(last));
    memset(inq, 0, sizeof(inq));
    memset(dis, 127, sizeof(dis));
    flow[s] = INF;
    dis[s] = 0;
    Q.push(s);
    while (!Q.empty())
    {
        int p = Q.front();
        Q.pop();
        inq[p] = 0;
        for (int eg = head[p]; eg != 0; eg = edges[eg].next)
        {
            int to = edges[eg].to, vol = edges[eg].w;
            if (vol > 0 && dis[to] > dis[p] + edges[eg].c) // 容量大于0才增广
            {
                last[to] = eg; // 记录上一条边
                flow[to] = min(flow[p], vol); // 更新下一个点的流量
                dis[to] = dis[p] + edges[eg].c; // 注意这里是c不是w
                if (!inq[to])
                {
                    Q.push(to);
                    inq[to] = 1;
                }
            }
        }
    }
    return last[t] != -1;
}
ll maxflow, mincost;
inline void MCMF() // 这里要求两个值，直接改成给全局变量赋值了，传pair也可以吧
{
    while (SPFA())
    {
		
        maxflow += flow[t];
        mincost += 1ll * dis[t] * flow[t];
        for (int i = t; i != s; i = edges[last[i] ^ 1].to)
        {
            edges[last[i]].w -= flow[t];
            edges[last[i] ^ 1].w += flow[t];
        }
    }
}
void init(){
	n=N*2+2;
	s=0,t=n-1;
	add(s,1,2,0);
	add(t-1,t,2,0);
	for(int i=1;i<=N;i++){
		int w=1;
		if(i==1||i==N)w=2;
		add(i*2-1,i*2,w,-1);
	}
	for(int i=1;i<=M;i++){
		string a,b;
		cin>>a>>b;
		int u=mp[a],v=mp[b];
		if(u>v)swap(u,v);
		add(u*2,v*2-1,2,0);
	}
}
vector<int>vec;
void dfs(int u){
	vec.push_back(u/2);
	for(int i=head[u];i;i=edges[i].next){
		int v=edges[i].to,w=edges[i].w;
		if(w<2){
			if(v==t)return;
			dfs(v+1);
			edges[i].w++;
			break;
		}
	}
}
void print(){
	dfs(2);
	for(auto x:vec)cout<<ct[x]<<'\n';
	vec.clear();
	dfs(2);
	vec.pop_back();
	reverse(vec.begin(),vec.end());
	for(auto x:vec)cout<<ct[x]<<'\n';
	
}
int main(){
	ios::sync_with_stdio(0);
	cin.tie(0);
	cin>>N>>M;
	for(int i=1;i<=N;i++){
		cin>>ct[i];
		mp[ct[i]]=i;
	}
	init();
	MCMF();
	if(maxflow!=2)cout<<"No Solution!"<<'\n';
	else {
		mincost=-mincost-2;
		if(n==1)mincost++;
		cout<<mincost<<'\n';
		print();
	}
	return 0;
}

最小路径覆盖问题

考虑每个点都是一条单独的路径，然后再合并点。于是把点拆成两个，对于一条边(u,v)，则连接(u2-1,v2)，跑得的最大流代表着最大的合并次数，所以答案就是总点数减去最大流。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int MAXN=1e5+100;
const int MAXM=5e5+5;
const int INF=1e9;

int N,M,nxt[MAXN],frt[MAXN];
vector<int>e[MAXN];
int n,m,s,t;
struct Edge{
    ll to, next, weight;
};
Edge edges[MAXM]; 
int edge_cnt = 1, head[MAXN], cur[MAXN];

void add(int x,int y,int w){
    edges[++edge_cnt].next = head[x];
    edges[edge_cnt].to = y;
    edges[edge_cnt].weight = w;
    head[x] = edge_cnt ;

    edges[++edge_cnt].next = head[y];
    edges[edge_cnt].to = x;
    edges[edge_cnt].weight = 0;
    head[y] = edge_cnt ;
}

int level[MAXN];
bool bfs(){
    memset(level, 0, sizeof(level));
    memcpy(cur, head, sizeof(head));
    queue<int> q;
    q.push(s);
    level[s] = 1;
    while (!q.empty()){
        int u = q.front();
        q.pop();
        for (int i = head[u]; i != 0; i = edges[i].next){
            ll v = edges[i].to, flow = edges[i].weight;
            if (flow > 0 && level[v] == 0){
                level[v] = level[u] + 1;
                q.push(v);
            }
        }   
    }
    return (level[t] != 0);
}

int dfs(int p = s, int cur_flow = INF){
    if (p == t) return cur_flow;
    ll ret = 0;
    for (int i = cur[p]; i != 0; i = edges[i].next){
        cur[p] = i;
        ll v = edges[i].to, vol = edges[i].weight;
        if (level[v] == level[p] + 1 && vol > 0){
            int f = dfs(v, min(cur_flow - ret, vol));
            edges[i].weight -= f;
            edges[i^1].weight += f;
            ret += f;
            if (ret == cur_flow) return ret;
        }
    }
    return ret;
}

ll dinic(){
    ll max_flow = 0;
    while (bfs()){
        max_flow += dfs();
    }
    return max_flow;
}
void init(){
	n=N*2+2;
	s=0,t=n-1;
	for(int i=1;i<=N;i++){
		add(0,i*2-1,1);
		add(i*2,t,1);
	}
	for(int i=1;i<=N;i++){
		for(auto v:e[i]){
			add(i*2-1,v*2,1);
		}
	}
}
void print(){
	for(int i=1;i<=N;i++){
		for(int j=head[i*2-1];j;j=edges[j].next){
			int v=edges[j].to/2,w=edges[j].weight;
			if(!w)nxt[i]=v,frt[v]=i;
		}
	}
	int cnt=0;
	for(int i=1;i<=N;i++){
		if(frt[i])continue;
		cnt++;
		for(int j=i;j;j=nxt[j]){
			cout<<j<<' ';
		}
		cout<<'\n';
	}
	cout<<cnt<<'\n';
}
int main(){
	ios::sync_with_stdio(0);
	cin.tie(0);
	cin>>N>>M;
	for(int i=1;i<=M;i++){
		int u,v;
		cin>>u>>v;
		e[u].push_back(v);
	}

	init();
	dinic();
	print();
	return 0;
}

[CTSC1999]家园 / 星际转移问题

首先二分需要的时间，然后拆点，构建分层图。即从上一时刻的空间站向着下一时刻的空间站连一条容量为INF的边，然后转移边就是每个飞船的行动路线，若路径经过i，j，则为从t-1时刻的i点到t时刻的j点。然后跑最大流查看是否为K就可。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int MAXN=1e5+100;
const int MAXM=5e5+5;
const int INF=1e9;

int N,M,K,sz[MAXN];
vector<int>e[MAXN],spot[MAXN];

int n,m,s,t;
struct Edge{
    ll to, next, weight;
};
Edge edges[MAXM]; 
int edge_cnt = 1, head[MAXN], cur[MAXN];

void add(int x,int y,int w){
    edges[++edge_cnt].next = head[x];
    edges[edge_cnt].to = y;
    edges[edge_cnt].weight = w;
    head[x] = edge_cnt ;

    edges[++edge_cnt].next = head[y];
    edges[edge_cnt].to = x;
    edges[edge_cnt].weight = 0;
    head[y] = edge_cnt ;
}

int level[MAXN];
bool bfs(){
    memset(level, 0, sizeof(level));
    memcpy(cur, head, sizeof(head));
    queue<int> q;
    q.push(s);
    level[s] = 1;
    while (!q.empty()){
        int u = q.front();
        q.pop();
        for (int i = head[u]; i != 0; i = edges[i].next){
            ll v = edges[i].to, flow = edges[i].weight;
            if (flow > 0 && level[v] == 0){
                level[v] = level[u] + 1;
                q.push(v);
            }
        }   
    }
    return (level[t] != 0);
}

int dfs(int p = s, int cur_flow = INF){
    if (p == t) return cur_flow;
    ll ret = 0;
    for (int i = cur[p]; i != 0; i = edges[i].next){
        cur[p] = i;
        ll v = edges[i].to, vol = edges[i].weight;
        if (level[v] == level[p] + 1 && vol > 0){
            int f = dfs(v, min(cur_flow - ret, vol));
            edges[i].weight -= f;
            edges[i^1].weight += f;
            ret += f;
            if (ret == cur_flow) return ret;
        }
    }
    return ret;
}

ll dinic(){
    ll max_flow = 0;
    while (bfs()){
        max_flow += dfs();
    }
    return max_flow;
}
bool check(int time){
    n=(N+2)*(time+1)+2;
    s=0,t=n-1,edge_cnt=1;
	memset(head,0,sizeof(head));
    for(int i=1;i<=time;i++){
        for(int j=1;j<=M;j++){
            int pre=spot[j][(i-1)%spot[j].size()]+(N+2)*(i-1);
            int nxt=spot[j][i%spot[j].size()]+(N+2)*i;
            add(pre,nxt,sz[j]);
        }
        for(int j=1;j<=N+2;j++){
            int pre=j+(N+2)*(i-1);
            int nxt=j+(N+2)*i;
            add(pre,nxt,INF);
        }
        add((N+2)*i+1,t,INF);
    }
    add(s,2,K);
    if(dinic()==K)return true;
    else return false;
}
int main(){
	ios::sync_with_stdio(0);
	cin.tie(0);
	cin>>N>>M>>K;
	for(int i=1;i<=M;i++){
        cin>>sz[i];
        int cnt;
        cin>>cnt;
        for(int j=1;j<=cnt;j++){
            int x;cin>>x;
            spot[i].push_back(x+2);
        }   
	}
    int l=1,r=751;
    while(l<r){
        int mid=l+r>>1;
        if(check(mid))r=mid;
        else l=mid+1;
    }
	if(l!=751)cout<<l<<'\n';
	else puts("0");
	return 0;
}

太空飞行计划问题

最小割的经典例题，还是挺有代表性的。

先说说如何建图：从源点连边到所有的实验，边权为实验的价值；从所有的实验器材到汇点连边，边权为器材的价格；对于每个实验，从该实验向着它所需要的器材连边，边权为INF。对所有的实验的价值求和，然后减去这个图上的最大流即为答案。

证明有很多，可以去洛谷的题解里面查看，这里简单介绍一下我的理解、

首先说明一下这个图中的割的含义：对于从源点连出的边，被割掉则表示不选择这条边，即没被割掉则表示选择该边；对于连向汇点的边，被割掉则表示选择这条边。这样一来，可以满足对于每个被选择的实验，其后继的实验器材一定被选择。所以一个合法的决策一定和该图的一个割对应。

易知答案=所有的实验的价值总和-一个合法的割的权值

所有实验的价值总和是定值，所以只需要最小化割的权值即可，所以最小割即为所求。

本题还有一个坑点在于输出方案。需要明确的是，不能利用跑完dinic后的边权余量来判断一条边是否被选择成为了割边。举个例子，一个实验价值为1，需要一个器材，该器材的花费也为1，所以跑完网络流后，这两条边的余量都是0，所以这个实验和器材要么都被选择，要么都不被选择，但是按照一般的逻辑来写的话，实验的边会被看成割掉，器材的边也会被看成被割掉，会导致输出方案错误。

如何解决呢？我们可以枚举每个实验，把它的边权设置为INF，表示这条边必须没有被割掉，如果这样算出来的最小割依然为原值，则说明这条边对应的实验一定在方案中。实验器材则可以直接通过已选择的实验确定。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int MAXN=1e3+100;
const int MAXM=5e4+5;
const int INF=1e9;

int M,N,ans;
int ex[MAXN],ep[MAXN];
vector<int>e[MAXN];
int n, m, s, t;

struct Edge{
    ll to, next, weight;
};
Edge edges[MAXM]; 
int edge_cnt = 1, head[MAXN], cur[MAXN];

void add(int x,int y,int w){
    edges[++edge_cnt].next = head[x];
    edges[edge_cnt].to = y;
    edges[edge_cnt].weight = w;
    head[x] = edge_cnt ;

    edges[++edge_cnt].next = head[y];
    edges[edge_cnt].to = x;
    edges[edge_cnt].weight = 0;
    head[y] = edge_cnt ;
}

int level[MAXN];
bool bfs(){
    memset(level, 0, sizeof(level));
    memcpy(cur, head, sizeof(head));
    queue<int> q;
    q.push(s);
    level[s] = 1;
    while (!q.empty()){
        int u = q.front();
        q.pop();
        for (int i = head[u]; i != 0; i = edges[i].next){
            ll v = edges[i].to, flow = edges[i].weight;
            if (flow > 0 && level[v] == 0){
                level[v] = level[u] + 1;
                q.push(v);
            }
        }   
    }
    return (level[t] != 0);
}

int dfs(int p = s, int cur_flow = INF){
    if (p == t) return cur_flow;
    ll ret = 0;
    for (int i = cur[p]; i != 0; i = edges[i].next){
        cur[p] = i;
        ll v = edges[i].to, vol = edges[i].weight;
        if (level[v] == level[p] + 1 && vol > 0){
            int f = dfs(v, min(cur_flow - ret, vol));
            edges[i].weight -= f;
            edges[i^1].weight += f;
            ret += f;
            if (ret == cur_flow) return ret;
        }
    }
    return ret;
}

ll dinic(){
    ll max_flow = 0;
    while (bfs()){
        max_flow += dfs();
    }
    return max_flow;
}
void init(){
	n=N+M+2;
	s=0,t=n-1;
	for(int i=1;i<=M;i++){
		add(s,i,ex[i]);
		for(auto j:e[i]){
			add(i,j+M,INF);
		}
	}
	for(int i=1;i<=N;i++){
		add(i+M,t,ep[i]);
	}
}
void scan(int i){
	char tools[10000];
	memset(tools,0,sizeof tools);
	cin.getline(tools,10000);
	int ulen=0,tool;
	while (sscanf(tools+ulen,"%d",&tool)==1)//之前已经用scanf读完了赞助商同意支付该实验的费用
	{//tool是该实验所需仪器的其中一个      
		//这一行，你可以将读进来的编号进行储存、处理，如连边。
		e[i].push_back(tool);
		if (tool==0) 
			ulen++;
		else {
			while (tool) {
				tool/=10;
				ulen++;
			}
		}
		ulen++;

	}
}
void clear(){
	edge_cnt=1;
	memset(head,0,sizeof(head));
}
int vis[2][MAXN];
vector<int>temp,a,b;
void print(){
	for(int i=head[s];i;i=edges[i].next)temp.push_back(i);
	for(auto it:temp){
		clear();
		init();
		ll w=edges[it].weight;
		ll &x=edges[it].weight;
		x=INF;
		if(dinic()==ans)vis[0][edges[it].to]=1;
	}
	for(int i=1;i<=M;i++){
		if(!vis[0][i])continue;
		for(auto j:e[i]){
			vis[1][j]=1;
		}
	}
	for(int i=1;i<=M;i++)if(vis[0][i])cout<<i<<' ';
	cout<<'\n';
	for(int i=1;i<=N;i++)if(vis[1][i])cout<<i<<' ';
	cout<<'\n';
}
int main(){
	ios::sync_with_stdio(0);
	cin.tie(0);
	cin>>M>>N;
	for(int i=1;i<=M;i++){
		cin>>ex[i];
		scan(i);
	}
	for(int i=1;i<=N;i++)cin>>ep[i];
	init();
	ans=dinic();
	print();
	for(int i=1;i<=M;i++)ans-=ex[i];
	cout<<-ans<<'\n';
	return 0;
}

最长k可重区间集问题

该题目的限制条件为同一个点上对应的区间数不得超过K

乍看之下很难用简洁的代码去描述这个限制。这里我们需要转换一下思维方式。

首先，由于区间是开区间，且端点值均为整数，所以我们可以把长度为1的线段看成考虑的基本元素。例如区间[i,i+1]代表的是其端点间所夹的长度为1的线段。

然后我们可以发现，除了区间端点之外的点，都不影响答案，所以可以离散化端点。

所以问题就转变为，如何找到一个区间集合，对于数轴上的每条长度为1的线段，覆盖它的区间不超过K

对于一个区间[l,r]，我们连接接一条从l点连接到r的点，其中覆盖了r-l条线段，分别为[l,l+1],[l+1,l+2],…,[r-1,r]，容量为1（因为一个区间只能最多选一次），价值为r-l

对于每两个相邻的点，连接一条容量为+∞的边，价值为0（走这条边相当于此时没有选区间）

我们构造一个源节点，将它放在数轴上的无穷远处，从该节点连出一条为容量为k的边到第一个线段（即同时只能在一个线段上选k个区间）

如果线段跨度比较大时，可以把端点离散化。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int,int>pii;
const int MAXN=4e3+5;
const int MAXM=2e4+5;
const int INF=1e9;
int N,K,idx;
map<int,int>mp;
pii seg[MAXN];
vector<int>pos;

int head[MAXN], cnt = 1;  // 这里特意把存图也贴出来，记住额外存一个参数c（费用）
struct Edge
{
    int to, w, c, next;
} edges[MAXM * 2];
inline void add(int from, int to, int w, int c)
{
    edges[++cnt].to = to;
    edges[cnt].w = w;
    edges[cnt].c = c;
    edges[cnt].next = head[from];
    head[from] = cnt;

	edges[++cnt].to = from;
	edges[cnt].w = 0;
	edges[cnt].c = -c;
	edges[cnt].next = head[to];
	head[to] = cnt;
	
}
int n, m, s, t, last[MAXN], flow[MAXN], inq[MAXN], dis[MAXN];
queue<int> Q;
bool SPFA()
{
    while (!Q.empty())
        Q.pop();
    memset(last, -1, sizeof(last));
    memset(inq, 0, sizeof(inq));
    memset(dis, 127, sizeof(dis));
    flow[s] = INF;
    dis[s] = 0;
    Q.push(s);
    while (!Q.empty())
    {
        int p = Q.front();
        Q.pop();
        inq[p] = 0;
        for (int eg = head[p]; eg != 0; eg = edges[eg].next)
        {
            int to = edges[eg].to, vol = edges[eg].w;
            if (vol > 0 && dis[to] > dis[p] + edges[eg].c) // 容量大于0才增广
            {
                last[to] = eg; // 记录上一条边
                flow[to] = min(flow[p], vol); // 更新下一个点的流量
                dis[to] = dis[p] + edges[eg].c; // 注意这里是c不是w
                if (!inq[to])
                {
                    Q.push(to);
                    inq[to] = 1;
                }
            }
        }
    }
    return last[t] != -1;
}
ll maxflow, mincost;
inline void MCMF() // 这里要求两个值，直接改成给全局变量赋值了，传pair也可以吧
{
    while (SPFA())
    {
        maxflow += flow[t];
        mincost += 1ll * dis[t] * flow[t];
        for (int i = t; i != s; i = edges[last[i] ^ 1].to)
        {
            edges[last[i]].w -= flow[t];
            edges[last[i] ^ 1].w += flow[t];
        }
    }
}
void init(){
	n=idx+2;
	s=0,t=n-1;
	add(s,1,K,0);
	for(int i=1;i<idx;i++){
		add(i,i+1,K,0);
	}
	for(int i=1;i<=N;i++){
		add(mp[seg[i].first],mp[seg[i].second],1,-seg[i].second+seg[i].first);
	}
	add(idx,t,K,0);
}
int main(){
	ios::sync_with_stdio(0);
	cin.tie(0);
	cin>>N>>K;
	pos.push_back(-2e9);
	for(int i=1;i<=N;i++){
		int x,y;
		cin>>x>>y;
		seg[i]={x,y};
		pos.push_back(x);
		pos.push_back(y);
	}
	sort(pos.begin(),pos.end());
	for(auto it:pos)if(!mp.count(it))mp[it]=++idx;
	init();
	MCMF();
	cout<<-mincost<<'\n';
	return 0;
}

最长k可重线段集问题

该问题的模型同上一题。注意考虑一下线段的特殊情况即可。这里把端点和端点之间的线段部分都看成独立的点。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int,int>pii;
const int MAXN=4e3+5;
const int MAXM=2e4+5;
const int INF=1e9;
int N,K,idx;
map<int,int>mp;
pii seg[MAXN];
int len[MAXN];
vector<int>pos;

int head[MAXN], cnt = 1;  // 这里特意把存图也贴出来，记住额外存一个参数c（费用）
struct Edge
{
    int to, w, next, c;
} edges[MAXM * 2];
inline void add(int from, int to, int w, int c)
{
    edges[++cnt].to = to;
    edges[cnt].w = w;
    edges[cnt].c = c;
    edges[cnt].next = head[from];
    head[from] = cnt;

	edges[++cnt].to = from;
	edges[cnt].w = 0;
	edges[cnt].c = -c;
	edges[cnt].next = head[to];
	head[to] = cnt;
	
}
int n, m, s, t, last[MAXN], flow[MAXN], inq[MAXN], dis[MAXN];
queue<int> Q;
bool SPFA()
{
    while (!Q.empty())
        Q.pop();
    memset(last, -1, sizeof(last));
    memset(inq, 0, sizeof(inq));
	memset(dis, 127, sizeof(dis));
    flow[s] = INF;
    dis[s] = 0;
    Q.push(s);
    while (!Q.empty())
    {
        int p = Q.front();
        Q.pop();
        inq[p] = 0;
        for (int eg = head[p]; eg != 0; eg = edges[eg].next)
        {
            int to = edges[eg].to, vol = edges[eg].w;
            if (vol > 0 && dis[to] > dis[p] + edges[eg].c) // 容量大于0才增广
            {
                last[to] = eg; // 记录上一条边
                flow[to] = min(flow[p], vol); // 更新下一个点的流量
                dis[to] = dis[p] + edges[eg].c; // 注意这里是c不是w
                if (!inq[to])
                {
                    Q.push(to);
                    inq[to] = 1;
                }
            }
        }
    }
    return last[t] != -1;
}
ll maxflow,mincost;
inline void MCMF() // 这里要求两个值，直接改成给全局变量赋值了，传pair也可以吧
{
    while (SPFA())
    {
        maxflow += flow[t];
        mincost += 1ll * dis[t] * flow[t];
        for (int i = t; i != s; i = edges[last[i] ^ 1].to)
        {
            edges[last[i]].w -= flow[t];
            edges[last[i] ^ 1].w += flow[t];
        }
    }
}
void init(){
	n=idx+2;
	s=0,t=n-1;
	add(s,1,K,0);
	for(int i=1;i<idx;i++){
		add(i,i+1,K,0);
	}
	for(int i=1;i<=N;i++){
		add(mp[seg[i].first],mp[seg[i].second],1,-len[i]);
	}
	add(idx,t,K,0);
}
ll ad;
int main(){
	ios::sync_with_stdio(0);
	cin.tie(0);
	cin>>N>>K;
	pos.push_back(-2e9);
	for(int i=1;i<=N;i++){
		int x1,x2,y1,y2;
		cin>>x1>>y1>>x2>>y2;
		if(x1>x2){
			swap(x1,x2);
			swap(y1,y2);
		}
		len[i]=(int)sqrt(1ll*(x1-x2)*(x1-x2)+1ll*(y1-y2)*(y1-y2));
		if(x1==x2){
			x1*=2;
			x2=x1+1;
		}
		else {
			x1=x1*2+1;
			x2=x2*2;
		}
		seg[i]={x1,x2};
		pos.push_back(x1);
		pos.push_back(x2);
	}
	sort(pos.begin(),pos.end());
	for(auto it:pos)if(!mp.count(it))mp[it]=++idx;
	init();
	MCMF();
	cout<<-mincost+ad<<'\n';
	return 0;
}

魔术球问题

问题的关键在于如何满足数字是连续的，这也是这道题与前面题目的不同之处。

考虑设计一个模型，使得一旦新的球被放到柱子上，流量便会增大。先说建图方式：将每个点拆成两个点，源点连向入点，出点连向汇点，边权都是1。然后对于能组成平方数的两个数对之间也连边，入点连向出点。

每次遇到一个新的球，就跑一边网络流，如果能跑通，说明当前这个球能被前面的某个球“接住”，否则必须额外新开一根柱子去放置这个球。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int MAXN=1e5+100;
const int MAXM=5e6+5;
const int INF=1e9;

int N,ans;
int ptr[MAXN],idx;

int n, m, s, t;

struct Edge{
    ll to, next, weight;
};
Edge edges[MAXM]; 
int edge_cnt = 1, head[MAXN], cur[MAXN];

void add(int x,int y,int w){
    edges[++edge_cnt].next = head[x];
    edges[edge_cnt].to = y;
    edges[edge_cnt].weight = w;
    head[x] = edge_cnt ;

    edges[++edge_cnt].next = head[y];
    edges[edge_cnt].to = x;
    edges[edge_cnt].weight = 0;
    head[y] = edge_cnt ;
}

int level[MAXN];
bool bfs(){
    memset(level, 0, sizeof(level));
    memcpy(cur, head, sizeof(head));
    queue<int> q;
    q.push(s);
    level[s] = 1;
    while (!q.empty()){
        int u = q.front();
        q.pop();
        for (int i = head[u]; i != 0; i = edges[i].next){
            ll v = edges[i].to, flow = edges[i].weight;
            if (flow > 0 && level[v] == 0){
                level[v] = level[u] + 1;
                q.push(v);
            }
        }   
    }
    return (level[t] != 0);
}

int dfs(int p = s, int cur_flow = INF){
    if (p == t) return cur_flow;
    ll ret = 0;
    for (int i = cur[p]; i != 0; i = edges[i].next){
        cur[p] = i;
        ll v = edges[i].to, vol = edges[i].weight;
        if (level[v] == level[p] + 1 && vol > 0){
            int f = dfs(v, min(cur_flow - ret, vol));
            edges[i].weight -= f;
            edges[i^1].weight += f;
            ret += f;
            if (ret == cur_flow) return ret;
        }
    }
    return ret;
}

ll dinic(){
    ll max_flow = 0;
    while (bfs()){
        max_flow += dfs();
    }
    return max_flow;
}
void init(){
	n=5000*2+2;
	s=0,t=n-1;
}
void print(){
	for(int i=1;i<idx;i++){
		for(int j=ptr[i];j;){
			cout<<j<<' ';
			int temp=0;
			for(int k=head[j*2-1];k;k=edges[k].next){
				if(!edges[k].weight){
					temp=edges[k].to/2;
					break;
				}
			}
			j=temp;
		}
		cout<<'\n';
	}
}
int main(){
	ios::sync_with_stdio(0);
	cin.tie(0);
	cin>>N;
	init();
	while(idx<=N){
		ans++;
		add(s,ans*2-1,1);
		add(ans*2,t,1);
		for(int i=sqrt(ans+0.5)+1;i*i<ans*2;i++){
			add((i*i-ans)*2-1,ans*2,1);
		}
		if(dinic()==0)ptr[++idx]=ans;
	}
	cout<<--ans<<'\n';
	print();
	return 0;
}

汽车加油行驶问题

观察到K比较小，于是比较容易地想到把当前的油量也看成一个状态，所以直接跑一个流量为1的最小费用流就行了。

注意车辆在一个地方最多被加满油一次，所以在没有加油站的地方加油时，可以直接把建加油站的钱加到油钱上面去，不需要单独判断。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int MAXN=2e5+5;
const int MAXM=2e6+5;
const int INF=1e9;
int N,K,A,B,C;
int a[105][105];

int head[MAXN], cnt = 1;  // 这里特意把存图也贴出来，记住额外存一个参数c（费用）
struct Edge
{
    int to, w, c, next;
} edges[MAXM * 2];
inline void add(int from, int to, int w, int c)
{
    edges[++cnt].to = to;
    edges[cnt].w = w;
    edges[cnt].c = c;
    edges[cnt].next = head[from];
    head[from] = cnt;

	edges[++cnt].to = from;
	edges[cnt].w = 0;
	edges[cnt].c = -c;
	edges[cnt].next = head[to];
	head[to] = cnt;
	
}
int n, m, s, t, last[MAXN], flow[MAXN], inq[MAXN], dis[MAXN];
queue<int> Q;
bool SPFA()
{
    while (!Q.empty())
        Q.pop();
    memset(last, -1, sizeof(last));
    memset(inq, 0, sizeof(inq));
    memset(dis, 127, sizeof(dis));
    flow[s] = INF;
    dis[s] = 0;
    Q.push(s);
    while (!Q.empty())
    {
        int p = Q.front();
        Q.pop();
        inq[p] = 0;
        for (int eg = head[p]; eg != 0; eg = edges[eg].next)
        {
            int to = edges[eg].to, vol = edges[eg].w;
            if (vol > 0 && dis[to] > dis[p] + edges[eg].c) // 容量大于0才增广
            {
                last[to] = eg; // 记录上一条边
                flow[to] = min(flow[p], vol); // 更新下一个点的流量
                dis[to] = dis[p] + edges[eg].c; // 注意这里是c不是w
                if (!inq[to])
                {
                    Q.push(to);
                    inq[to] = 1;
                }
            }
        }
    }
    return last[t] != -1;
}
ll maxflow, mincost;
inline void MCMF() // 这里要求两个值，直接改成给全局变量赋值了，传pair也可以吧
{
    while (SPFA())
    {
        maxflow += flow[t];
        mincost += 1ll * dis[t] * flow[t];
        for (int i = t; i != s; i = edges[last[i] ^ 1].to)
        {
            edges[last[i]].w -= flow[t];
            edges[last[i] ^ 1].w += flow[t];
        }
    }
}
int id(int x,int y,int k){
	return ((x-1)*N+y-1)*11+k+1;
}
int dx[4]={0,0,1,-1};
int dy[4]={1,-1,0,0};
void init(){
	n=id(N,N,K)+2;
	s=0,t=n-1;
	add(s,id(1,1,K),1,0);
	for(int i=1;i<=N;i++){
		for(int j=1;j<=N;j++){
			for(int k=1;k<=K;k++){
				int cur=id(i,j,k);
				for(int t=0;t<4;t++){
					int ni=i+dx[t];
					int nj=j+dy[t];
					if(!ni||ni>N)continue;
					if(!nj||nj>N)continue;
					int cst=0,val=k-1;
					if(ni<i||nj<j)cst+=B;
					if(a[ni][nj])val=K,cst+=A;
					int to=id(ni,nj,val);
					add(cur,to,1,cst);
				}
			}
			if(!a[i][j]){
				for(int k=0;k<K;k++){
					int cur=id(i,j,k);
					int to=id(i,j,K);
					add(cur,to,1,C+A);
				}
			}
		}
	}
	for(int i=0;i<=K;i++)add(id(N,N,i),t,1,0);
}
int main(){
	ios::sync_with_stdio(0);
	cin.tie(0);
	cin>>N>>K>>A>>B>>C;
	for(int i=1;i<=N;i++){
		for(int j=1;j<=N;j++){
			cin>>a[i][j];
		}
	}
	init();
	MCMF();
	cout<<mincost<<'\n';
	return 0;
}

负载平衡问题

直接说建图吧，如果一个仓库当前的货物量大于平均值sum，则从源点连一条容量为a[i]-sum的边，否则从仓库连向汇点，容量为sum-a[i]，这两种边的费用均为零。然后在相邻点之间连容量为INF，费用为1的边。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int MAXN=4e3+5;
const int MAXM=2e4+5;
const int INF=1e9;
int N;
int a[MAXN];

int head[MAXN], cnt = 1;  // 这里特意把存图也贴出来，记住额外存一个参数c（费用）
struct Edge
{
    int to, w, c, next;
} edges[MAXM * 2];
inline void add(int from, int to, int w, int c)
{
    edges[++cnt].to = to;
    edges[cnt].w = w;
    edges[cnt].c = c;
    edges[cnt].next = head[from];
    head[from] = cnt;

	edges[++cnt].to = from;
	edges[cnt].w = 0;
	edges[cnt].c = -c;
	edges[cnt].next = head[to];
	head[to] = cnt;
	
}
int n, m, s, t, last[MAXN], flow[MAXN], inq[MAXN], dis[MAXN];
queue<int> Q;
bool SPFA()
{
    while (!Q.empty())
        Q.pop();
    memset(last, -1, sizeof(last));
    memset(inq, 0, sizeof(inq));
    memset(dis, 127, sizeof(dis));
    flow[s] = INF;
    dis[s] = 0;
    Q.push(s);
    while (!Q.empty())
    {
        int p = Q.front();
        Q.pop();
        inq[p] = 0;
        for (int eg = head[p]; eg != 0; eg = edges[eg].next)
        {
            int to = edges[eg].to, vol = edges[eg].w;
            if (vol > 0 && dis[to] > dis[p] + edges[eg].c) // 容量大于0才增广
            {
                last[to] = eg; // 记录上一条边
                flow[to] = min(flow[p], vol); // 更新下一个点的流量
                dis[to] = dis[p] + edges[eg].c; // 注意这里是c不是w
                if (!inq[to])
                {
                    Q.push(to);
                    inq[to] = 1;
                }
            }
        }
    }
    return last[t] != -1;
}
ll maxflow, mincost;
inline void MCMF() // 这里要求两个值，直接改成给全局变量赋值了，传pair也可以吧
{
    while (SPFA())
    {
        maxflow += flow[t];
        mincost += 1ll * dis[t] * flow[t];
        for (int i = t; i != s; i = edges[last[i] ^ 1].to)
        {
            edges[last[i]].w -= flow[t];
            edges[last[i] ^ 1].w += flow[t];
        }
    }
}
ll sum=0;
void init(){
	n=N+2;
	s=0,t=n-1;
	for(int i=1;i<=N;i++){
		if(a[i]>sum)add(s,i,a[i]-sum,0);
		if(a[i]<sum)add(i,t,sum-a[i],0);
	}
	for(int i=1;i<N;i++){
		add(i,i+1,INF,1);
		add(i+1,i,INF,1);
	}
	add(1,N,INF,1);
	add(N,1,INF,1);
}
int main(){
	ios::sync_with_stdio(0);
	cin.tie(0);
	cin>>N;
	for(int i=1;i<=N;i++)cin>>a[i],sum+=a[i];
	sum/=N;
	init();
	MCMF();
	cout<<mincost<<'\n';
	return 0;
}

火星探险问题

建图很简单，拆点就完了。

难点在于输出，这里使用了深搜的方式，详见代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int MAXN=8e3+5;
const int MAXM=8e4+5;
const int INF=1e9;
int N,p,q;
int a[40][40];
int dx[2]={1,0};
int dy[2]={0,1};
int head[MAXN], cnt = 1;  // 这里特意把存图也贴出来，记住额外存一个参数c（费用）
struct Edge
{
    int to, w, c, next;
} edges[MAXM * 2];
inline void add(int from, int to, int w, int c)
{
    edges[++cnt].to = to;
    edges[cnt].w = w;
    edges[cnt].c = c;
    edges[cnt].next = head[from];
    head[from] = cnt;

	edges[++cnt].to = from;
	edges[cnt].w = 0;
	edges[cnt].c = -c;
	edges[cnt].next = head[to];
	head[to] = cnt;
	
}
int n, m, s, t, last[MAXN], flow[MAXN], inq[MAXN], dis[MAXN];
queue<int> Q;
bool SPFA()
{
    while (!Q.empty())
        Q.pop();
    memset(last, -1, sizeof(last));
    memset(inq, 0, sizeof(inq));
    memset(dis, 127, sizeof(dis));
    flow[s] = INF;
    dis[s] = 0;
    Q.push(s);
    while (!Q.empty())
    {
        int p = Q.front();
        Q.pop();
        inq[p] = 0;
        for (int eg = head[p]; eg != 0; eg = edges[eg].next)
        {
            int to = edges[eg].to, vol = edges[eg].w;
            if (vol > 0 && dis[to] > dis[p] + edges[eg].c) // 容量大于0才增广
            {
                last[to] = eg; // 记录上一条边
                flow[to] = min(flow[p], vol); // 更新下一个点的流量
                dis[to] = dis[p] + edges[eg].c; // 注意这里是c不是w
                if (!inq[to])
                {
                    Q.push(to);
                    inq[to] = 1;
                }
            }
        }
    }
    return last[t] != -1;
}
ll maxflow, mincost;
inline void MCMF() // 这里要求两个值，直接改成给全局变量赋值了，传pair也可以吧
{
    while (SPFA())
    {
        maxflow += flow[t];
        mincost += 1ll * dis[t] * flow[t];
        for (int i = t; i != s; i = edges[last[i] ^ 1].to)
        {
            edges[last[i]].w -= flow[t];
            edges[last[i] ^ 1].w += flow[t];
        }
    }
}
int id(int x,int y,int t){
	return ((x-1)*q+y-1)*3+t;
}
void init(){
	n=id(p,q,3)+2;
	s=0,t=n-1;
	add(s,id(1,1,1),N,0);
	for(int i=1;i<=p;i++){
		for(int j=1;j<=q;j++){
			if(a[i][j]==2)
				add(id(i,j,1),id(i,j,2),1,-1),
				add(id(i,j,1),id(i,j,3),INF,0);
			for(int t=0;t<2;t++){
				int ni=dx[t]+i;
				int nj=dy[t]+j;
				if(ni>p||!ni)continue;
				if(nj>q||!nj)continue;
				if(a[i][j]==2){
					add(id(i,j,2),id(ni,nj,1),INF,0);
					add(id(i,j,3),id(ni,nj,1),INF,0);
				}
				else if(a[i][j]==0){
					add(id(i,j,1),id(ni,nj,1),INF,0);
				}
			}
		}
	}
	if(a[p][q]!=1){
		if(a[p][q]==2){
			add(id(p,q,2),t,INF,0);
			add(id(p,q,3),t,INF,0);
		}
		else {
			add(id(p,q,1),t,INF,0);
		}
	}
}
void print(int row,int col,int l,int r){
	if(r<l)return;
	// cout<<row<<' '<<col<<"$$\n";
	int cnt=r-l+1;
	for(int i=0;i<2;i++){
		int ni=dx[i]+row;
		int nj=dy[i]+col;
		if(ni>p||!ni)continue;
		if(nj>q||!nj)continue;
		for(int j=head[id(ni,nj,1)];j;j=edges[j].next){
			if(edges[j].to>id(ni,nj,1))continue;
			int &w=edges[j].w;
			for(int k=l;k<=l+min(w,cnt)-1;k++)cout<<k<<" "<<i<<'\n';
			int temp=min(w,cnt);
			w-=temp;
			cnt-=temp;
			print(ni,nj,l,l+temp-1);
			l+=temp;
		}
	}
}
int main(){
	ios::sync_with_stdio(0);
	cin.tie(0);
	cin>>N>>q>>p;
	for(int i=1;i<=p;i++)
	for(int j=1;j<=q;j++)
		cin>>a[i][j];
	init();
	MCMF();
	print(1,1,1,N);
	// cout<<-mincost<<'\n';
	return 0;
}

最长不下降子序列问题

方格取数问题

软件补丁问题

飞行员配对方案问题

数字梯形问题