周五cf补题

周五补题

A

求诱导子图,使得诱导子图的点的权重的和比上边权的和最大。

题解

要么选两个点,要么选一个点。后来感觉这种最大的东西,往往可能会是一种特殊的情形。

C

记住有模运算的时候,若产生负数,一定要加一个mod!!!!!以后不论如何都要加mod!!!!!

F

删掉不超过两条边,使得s到t点的不连通

题解

先找到一条路,若不连通,直接输出0
若连通,枚举这条路径上面的每一条边,删掉改边。若删掉边后,图不连通,表明要删掉的边为1,否则取找割。

AC code

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
#include <bits/stdc++.h>
using namespace std;
const int maxn = 1e3+10;
const int maxm = 6e4+10;
struct Edge{
int v,next,c;
}edge[maxm];
int head[maxn];
int tot;
int s,t;
int vis[maxn];
int dfn[maxn];
int low[maxn];
int bridge[maxm];
int Index;
void init(){
memset(head,-1, sizeof(head));
memset(vis,0, sizeof(vis));
tot=0;
}
void add_edge(int u,int v,int c){
edge[tot].v = v;
edge[tot].next = head[u];
edge[tot].c = c;
head[u]=tot++;
}
bool dfs(int u,int fa,int del, vector<int>& path){
vis[u]=1;
if(u==t) return true;
for(int i=head[u];i!=-1;i=edge[i].next){
int v=edge[i].v;
if(v==fa||(i>>1)==del) continue;
if(!vis[v]&&dfs(v,u,del,path)){
path.push_back(i>>1);
return true;
}
}
return false;
}
void tarjan(int u,int fa,int del){
dfn[u]=low[u]=++Index;
int flag=0;
for(int i=head[u];i!=-1;i=edge[i].next){
int v=edge[i].v;
if((i>>1)==del) continue;
if(v==fa&&!flag){
flag=1;
continue;
}
if(!dfn[v]){
tarjan(v,u,del);
low[u]=min(low[v],low[u]);
if(low[v]>dfn[u]) bridge[i>>1]=1;
}
else low[u]=min(dfn[v],low[u]);
}
}
int main(){
int n,m;
scanf("%d%d", &n, &m);
{
scanf("%d%d", &s, &t);
init();
for(int i=0;i<m;i++){
int a,b,c;
scanf("%d%d%d",&a,&b,&c);
add_edge(a,b,c);
add_edge(b,a,c);
}
vector<int> path;
path.clear();
if(!dfs(s,-1,-1,path)){
printf("0\n0\n");
}
else{
int ans=2e9+1;
vector<int> ret;
ret.clear();
for(int i=0;i<path.size();i++){
memset(dfn,0, sizeof(dfn));
memset(bridge,0, sizeof(bridge));
memset(vis,0, sizeof(vis));
Index=0;
//cout<<path[i]<<endl;
for(int j=1;j<=n;j++){
if(!dfn[j]) tarjan(j,-1,path[i]);
}
vector<int> tmp;
//边的编号是从0开始的
//删一条边后直接不连通
if(!dfs(s,-1,path[i],tmp)){
if(ans>edge[path[i]*2].c){
ans=edge[path[i]*2].c;
ret.clear();
ret.push_back(path[i]+1);
}
}
else{
//两条边后不连通
for(int j=0;j<tmp.size();j++){
if(bridge[tmp[j]]){
if(ans>edge[path[i]*2].c+edge[tmp[j]*2].c){
ans=edge[path[i]*2].c+edge[tmp[j]*2].c;
ret.clear();
ret.push_back(path[i]+1);
ret.push_back(tmp[j]+1);
}
}
}
}
}
if(ans>2e9) printf("-1\n");
else{
printf("%d\n%d\n", ans, ret.size());
for(int i=0;i<ret.size();i++){
printf("%d",ret[i]);
if(i==ret.size()-1) puts("");
else printf(" ");
}
}
}
}
return 0;
}

未解决的问题

文章目录
  1. 1. A
    1. 1.1. 题解
  2. 2. C
  3. 3. F
    1. 3.1. 题解
    2. 3.2. AC code
  4. 4. 未解决的问题
{{ live2d() }}