隐藏
「成都七中D6T1」盛夏 - 最小割 | Bill Yang's Blog

路终会有尽头,但视野总能看到更远的地方。

0%

「成都七中D6T1」盛夏 - 最小割

题目大意

    这是第三题,有趣的是这套题都是送分题。
    给定一个$N$个点$M$条边的有向无环图。每条边有一个边权。
    你想删去图中的一些边,使得对于任意一条从$1$到$N$的路径,都恰好有且只有一条此路径上的边被删掉。
    求删去的所有边边权和最小是多少。

题目分析

第一眼原图跑最小割,第二眼卧槽不会做。
考完后问achen怎么写的。
achen:“T3一眼题啊,最小割啊!”
Bill_Yang:“什么最小割。”
achen:“原图跑最小割!”

我们可以很轻松地构造出反例。

我们可以考虑对于原图的每一条边,建立一条容量为$inf$的反边。
再跑最小割即为答案。

我们分三步证明。

  • 上述转化可以解决在原图跑最小割的问题
  • 上述转化对原图跑最小割不存在其他影响
  • 上述转化具有最优性

对于第一个问题,我们可以考虑何时会有一条路径被两次切割。

  • 首先,若切割的两条边间的路径无其他边,显然是不优的。
  • 若切割的两条边间有入边或出边,显然同样不优,可以不用割去某一条边。
  • 若切割的两条边间有两条边,呈以下形状:

    显然,当前的割不满足要求。
  • 若切割的两条边间有两条边,呈以下形状:

    因为反边的存在,当前割不满足要求。

以此类推,我们可以证明以上转化可以解决反例的问题。
接下来我们证明第二个问题。
因为我们添加的是反边,而原图是一个DAG,故不会对原图跑最小割的产生其他影响。
第三个问题就很显然了,添加的容量为$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
153
154
155
156
157
158
159
160
161
162
163
164
165
#include<algorithm>
#include<iostream>
#include<iomanip>
#include<cstring>
#include<cstdlib>
#include<climits>
#include<vector>
#include<cstdio>
#include<cmath>
#include<queue>
using namespace std;

inline const int Get_Int() {
int num=0,bj=1;
char x=getchar();
while(x<'0'||x>'9') {
if(x=='-')bj=-1;
x=getchar();
}
while(x>='0'&&x<='9') {
num=num*10+x-'0';
x=getchar();
}
return num*bj;
}

int n,m;

namespace Solve1 {
const int maxn=25;

struct Edge {
int from,to,id;
};

int ans=INT_MAX,val[maxn],vst[maxn],bj,Del[maxn];
vector<Edge>edges[maxn];

void AddEdge(int x,int y,int id) {
edges[x].push_back((Edge) {x,y,id});
}

void Dfs(int Now,int sum) {
if(sum==2) {
bj=0;
return;
}
if(Now==n) {
if(sum==0)bj=0;
return;
}
for(int i=0; i<edges[Now].size(); i++) {
Edge& e=edges[Now][i];
int Next=e.to;
if(Del[e.id])Dfs(Next,sum+1);
else Dfs(Next,sum);
}
}

void solve() {
for(int i=1; i<=m; i++) {
int x=Get_Int(),y=Get_Int();
AddEdge(x,y,i);
val[i]=Get_Int();
}
for(int s=0; s<(1<<m); s++) {
int sum=0;
for(int i=1; i<=m; i++)
if(s&(1<<(i-1)))Del[i]=1,sum+=val[i];
else Del[i]=0;
bj=1;
Dfs(1,0);
if(bj)ans=min(ans,sum);
}
printf("%d\n",ans);
}
}

const int maxn=305;

struct Edge {
int from,to,cap,flow;
Edge(int x=0,int y=0,int c=0,int f=0):from(x),to(y),cap(c),flow(f) {}
};
struct Dinic {
int n,m,s,t;
vector<Edge>edges;
vector<int>G[maxn];
bool vst[maxn];
int dist[maxn],cur[maxn];
void init(int n) {
this->n=n;
edges.clear();
for(int i=1; i<=n; i++)G[i].clear();
}
void AddEdge(int x,int y,int v) {
edges.push_back(Edge(x,y,v,0));
edges.push_back(Edge(y,x,0,0));
m=edges.size();
G[x].push_back(m-2);
G[y].push_back(m-1);
}
bool bfs() {
memset(vst,0,sizeof(vst));
memset(dist,0,sizeof(dist));
queue<int>Q;
Q.push(t);
vst[t]=1;
while(!Q.empty()) {
int Now=Q.front();
Q.pop();
for(int i=0; i<G[Now].size(); i++) {
int id=G[Now][i];
Edge& e=edges[id^1];
int Next=e.from;
if(!vst[Next]&&e.cap>e.flow) {
vst[Next]=1;
dist[Next]=dist[Now]+1;
Q.push(Next);
}
}
}
return vst[s];
}
int dfs(int Now,int a) {
if(Now==t||a==0)return a;
int flow=0;
for(int& i=cur[Now]; i<G[Now].size(); i++) {
Edge& e=edges[G[Now][i]];
int Next=e.to;
if(dist[Now]-1!=dist[Next])continue;
int nextflow=dfs(Next,min(a,e.cap-e.flow));
if(nextflow>0) {
e.flow+=nextflow;
edges[G[Now][i]^1].flow-=nextflow;
flow+=nextflow;
a-=nextflow;
if(a==0)break;
}
}
return flow;
}
int maxflow(int s,int t) {
this->s=s;
this->t=t;
int flow=0;
while(bfs()) {
memset(cur,0,sizeof(cur));
flow+=dfs(s,INT_MAX);
}
return flow;
}
} dinic;

int main() {
n=Get_Int();
m=Get_Int();
for(int i=1; i<=m; i++) {
int x=Get_Int(),y=Get_Int(),v=Get_Int();
dinic.AddEdge(x,y,v);
dinic.AddEdge(y,x,INT_MAX);
}
printf("%d\n",dinic.maxflow(1,n));
return 0;
}
姥爷们赏瓶冰阔落吧~