最短路
这部分用wiki的即可
网络瘤
最大流
dinic
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
| #include<iostream>
#include<cmath>
#include<cstdio>
#include<cstring>
#include<queue>
#include<stack>
#include<vector>
#include<set>
#include<map>
#include<algorithm>
using namespace std;
const int maxn=20020;
int head[maxn],size=1,st,ed,ans,n,m;
int dep[maxn],vis[maxn];
int nt[maxn];
struct edge{
int next,to,dis;
int flow;
}e[maxn*10];
inline void addedge(int next,int to,int flow)
{
e[++size].to=to;
e[size].next=head[next];
e[size].flow=flow;
head[next]=size;
}
inline int bfs(int st)
{
queue <int> q;
memset(vis,0,sizeof(vis));
memset(dep,0,sizeof(dep));
q.push(st);
vis[st]=1;
while(!q.empty())
{
int t=q.front();
q.pop();
int i,j,k;
for(i=head[t];i;i=e[i].next)
{
j=e[i].to;
k=e[i].flow;
if(vis[j]||dep[j]||k<=0) continue;
dep[j]=dep[t]+1;q.push(j);
vis[j]=1;
}
}
return vis[ed];
}
int dfs(int t,int nowt)
{
if(t==ed||!nowt) return nowt;
int tot=0;
int j,k;
for(int &i=nt[t];i;i=e[i].next)
{
j=e[i].to;
k=e[i].flow;
if(k>0&&dep[j]==dep[t]+1)
{
int f=dfs(j,min(k,nowt-tot));
e[i].flow-=f;
e[i^1].flow+=f;
tot+=f;
if(nowt==tot) return tot;
}
}
return tot;
}
void dinic()
{
int i;
while(bfs(st))
{
for(i=1;i<=n;i++) nt[i]=head[i];
ans+=dfs(st,0x3f3f3f3f);
}
}
int main()
{
ios::sync_with_stdio(false);
register int i,j;
cin>>n>>m>>st>>ed;
int t1,t2,t3;
for(i=1;i<=m;i++)
{
cin>>t1>>t2>>t3;
addedge(t1,t2,t3);
addedge(t2,t1,0);
}
dinic();
cout<<ans<<endl;
return 0;
}
|
isap
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<stdio.h>
#include<iostream>
#include<cmath>
#include<cstring>
#include<queue>
#include<stack>
#include<vector>
#include<set>
#include<map>
#include<algorithm>
#define int long long
using namespace std;
const int maxn=5200;
int head[maxn],dep[maxn],size=1,nhead[maxn];
int n,m,st,ed;
int gap[maxn];
struct edge{
int next,to,flow;
}e[maxn<<1];
inline void addedge(int next,int to,int flow)
{
e[++size].to=to;
e[size].flow=flow;
e[size].next=head[next];
head[next]=size;
e[++size].to=next;
e[size].flow=0;
e[size].next=head[to];
head[to]=size;
}
inline void getdis()
{
queue <int> q;
q.push(ed);
memset(gap,0,sizeof(gap)); memset(dep,0,sizeof(dep));
for(int i=1;i<=n;i++) nhead[i]=head[i];
++gap[dep[ed]=1];
while(!q.empty())
{
int t=q.front();
q.pop();
int i,j,k;
for(i=head[t];i;i=e[i].next)
{
j=e[i].to;
if(!dep[j]) dep[j]=dep[t]+1,gap[dep[j]]++,q.push(j);
}
}
}
int isap(int t,int nowflow)
{
if(t==ed||!nowflow) return nowflow;
int j,k,f,tot=0;
for(int &i=nhead[t];i;i=e[i].next)
{
j=e[i].to; k=e[i].flow;
if(dep[j]==dep[t]-1)
{
f=isap(j,min(nowflow-tot,k));
e[i].flow-=f;
e[i^1].flow+=f;
tot+=f;
if(tot==nowflow) return tot;
}
}
if(!(--gap[dep[t]])) dep[st]=n+1;
++gap[++dep[t]];
nhead[t]=head[t];
return tot;
}
inline int getans()
{
int ans=0;
getdis();
ans=isap(st,0x3f3f3f3f);
while(dep[st]<=n) ans+=isap(st,0x3f3f3f3f);
return ans;
}
signed main()
{
ios::sync_with_stdio(false);
register int i,j;
cin>>n>>m>>st>>ed;
int t1,t2,t3;
for(i=1;i<=m;i++)
{
cin>>t1>>t2>>t3;
addedge(t1,t2,t3);
}
cout<<getans()<<endl;
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
| #include<iostream>
#include<cmath>
#include<cstdio>
#include<cstring>
#include<queue>
#include<stack>
#include<vector>
#include<set>
#include<map>
#include<algorithm>
using namespace std;
const int maxn=10080;
int head[maxn],nt[maxn],size=1,mcost,mflow;
int pre[maxn],las[maxn],flow[maxn];
int vis[maxn],dis[maxn];
int st,ed,n,m;
struct node{
int next,to,dis,flow;
}e[maxn*20];
inline void addedge(int next,int to,int dis,int flow)
{
e[++size].to=to;
e[size].dis=dis;
e[size].flow=flow;
e[size].next=head[next];
head[next]=size;
}
inline int spfa()
{
queue <int> q;
memset(vis,0,sizeof(vis));
memset(dis,0x3f,sizeof(dis));
memset(flow,0x3f,sizeof(flow));
memset(pre,0,sizeof(pre));
dis[st]=0;
vis[st]=1;
las[st]=0;
pre[st]=0;
q.push(st);
while(!q.empty())
{
int t=q.front();
q.pop();
vis[t]=0;
int i,j,k,l;
for(i=head[t];i;i=e[i].next)
{
j=e[i].to;
k=e[i].dis;
l=e[i].flow;
if(dis[t]+k<dis[j]&&l>0)
{
flow[j]=min(l,flow[t]);
dis[j]=dis[t]+k;
pre[j]=t;
las[j]=i;
if(!vis[j]) vis[j]=1,q.push(j);
}
}
}
return pre[ed];
}
inline void mcmf()
{
int i;
while(spfa())
{
int t=ed;
mflow+=flow[ed];
mcost+=dis[ed]*flow[ed];
for(i=ed;i!=st;i=pre[i])
{
e[las[i]].flow-=flow[ed];
e[las[i]^1].flow+=flow[ed];
}
}
}
int main()
{
ios::sync_with_stdio(false);
register int i,j;
cin>>n>>m>>st>>ed;
int t1,t2,t3,t4;
for(i=1;i<=m;i++)
{
cin>>t1>>t2>>t3>>t4;
addedge(t1,t2,t4,t3);
addedge(t2,t1,-t4,0);
}
mcmf();
cout<<mflow<<" "<<mcost;
}
|
二分图
二分图最大权完美匹配，KM
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
| #include<stdio.h>
#include<iostream>
#include<cmath>
#include<cstring>
#include<queue>
#include<stack>
#include<vector>
#include<set>
#include<map>
#include<algorithm>
#define int long long
using namespace std;
const int maxn=550;
int dis[maxn][maxn],match[maxn];
int etx[maxn],ety[maxn];
int slack[maxn],pre[maxn],vis[maxn];
int n,m,ans;
void bfs(int st)
{
memset(pre,0,sizeof(pre));
memset(slack,0x3f,sizeof(slack));
int t=0,tt=0;
match[tt]=st;
int i;
do
{
int dmmn=0x3f3f3f3f3f3f3f3f;
t=match[tt];
vis[tt]=1;
int nxt=0;
for(i=1;i<=n;i++)
{
if(vis[i]) continue;
if(slack[i]>etx[t]+ety[i]-dis[t][i]) slack[i]=etx[t]+ety[i]-dis[t][i],pre[i]=tt;
if(slack[i]<dmmn) dmmn=slack[i],nxt=i;
}
for(i=0;i<=n;i++)
{
if(vis[i]) etx[match[i]]-=dmmn,ety[i]+=dmmn;
else slack[i]-=dmmn;
}
tt=nxt;
}while(match[tt]);
while(tt) match[tt]=match[pre[tt]],tt=pre[tt];
}
void km()
{
memset(etx,0,sizeof(etx));
memset(ety,0,sizeof(ety));
memset(match,0,sizeof(match));
for(int i=1;i<=n;i++)
{
memset(vis,0,sizeof(vis));
bfs(i);
}
for(int i=1;i<=n;i++) ans+=dis[match[i]][i];
cout<<ans<<endl;
for(int i=1;i<=n;i++) cout<<match[i]<<" ";
return ;
}
signed main()
{
ios::sync_with_stdio(false);
register int i,j;
cin>>n>>m;
int t1,t2,t3;
for(i=1;i<=n;i++)
for(j=1;j<=n;j++)
dis[i][j]=-0x3f3f3f3f3f3f3f3f;
for(i=1;i<=m;i++)
{
cin>>t1>>t2>>t3;
dis[t1][t2]=t3;
}
km();
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
| #include<iostream>
#include<cmath>
#include<cstdio>
#include<cstring>
#include<queue>
#include<stack>
#include<vector>
using namespace std;
int head[10086],size,n,m,ee,have_meizi[10086],tot,vis[100860];
struct edge{
int next,to;
}e[1008600];
void addedge(int next,int to)
{
e[++size].next=head[next];
e[size].to=to;
head[next]=size;
}
int ycl(int a)
{
return a+n;
}
int hungary(int s)
{
int i,j;
for(i=head[s];i;i=e[i].next)
{
j=e[i].to;
if(vis[j]) continue;
vis[j]=1;
if(!have_meizi[j])
{
have_meizi[j]=s;
return 1;
}
else
{
if(hungary(have_meizi[j]))
{
have_meizi[j]=s;
return 1;
}
}
}
return 0;
}
int main()
{
int i,j;
scanf("%d %d %d",&n,&m,&ee);
for(i=1;i<=ee;i++)
{
int t1,t2;
scanf("%d %d",&t1,&t2);
if(t1>n||t2>m||t1>m||t2>n) continue;
addedge(t1,t2);
}
for(i=1;i<=m;i++)
{
memset(vis,0,sizeof(vis));
if(hungary(i)) tot++;
}
printf("%d",tot);
return 0;
}
|
prufer
【模板】Prufer 序列
题目描述
请实现 Prufer 序列和无根树的相互转化。
为方便你实现代码，尽管是无根树，我们在读入时仍将 n 设为其根。
对于一棵无根树，设 f1…n−1 为其父亲序列（fi 表示 i 在 n 为根时的父亲），设 p1…n−2 为其 Prufer 序列。
另外，对于一个长度为 m 的序列 a1…m，我们设其权值为 xori=1mi×ai。
输入格式
第一行两个整数 n,m，表示树的点数和转化类型。
若 m=1，第二行一行 n−1 个整数，表示父亲序列。
若 m=2，第二行一行 n−2 个整数，表示 Prufer 序列。
输出格式
若 m=1，一行一个整数，表示给出的父亲序列对应的 Prufer 序列的权值。
若 m=2，一行一个整数，表示给出的 Prufer 序列对应的父亲序列的权值。
样例 #1
样例输入 #1
样例输出 #1
样例 #2
样例输入 #2
样例输出 #2
prufer编码
cayley公式[n]含有nn−2棵树
prufer编码，f(T)=(a1,a2,...,an−2),ai表示编号最小的叶节点相邻节点（动态拆树）
显然这这东西对应回去的树一一对应，因此nn−2恰好对应了cayley公式（实际上这东西就是用来证明cayley的）
这东西证明cayley要证明一一对应的关系（双射）
考虑如何构造，发现当前位置的prufer序列是最小的叶子节点，我们把叶子节点都先丢进一个堆，然后每次取堆首的时候顺便把他的父亲放进堆里面，时间复杂度O(nlogn)事实证明本题的瓶颈还是在读入上面，所以把读入整好了也是能过的（
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
| inline void getpprufer()
{
int i;
for(i=1;i<=n-1;i++) d[a[i]]++;
priority_queue <int> q;
for(i=1;i<=n-1;i++) if(!d[i]) q.push(-i);
int cnt=0;
while(!q.empty())
{
if(cnt==n-2) break;
int t=q.top();
t=-t;
q.pop();
prufer[++cnt]=a[t];
d[a[t]]--;
if(!d[a[t]]) q.push(-a[t]);
}
int ans=0;
for(i=1;i<=n-2;i++) ans^=(i*prufer[i]);
cout<<ans<<endl;
}
|
考虑还原这棵树，不难发现不在prufer序列上面的点一定是叶子节点（度为1），我们每次就找到最小的叶子节点，然后就可以根据prufer序列来还原（得到父亲）
这样时间复杂度太高了，实际上我们每次找第一个的时候就只有两种情况，第一个更小和更大，更大的话很好做，直接用一个指针扫，变小就直接一个while循环到变大或者结束，时间复杂度是O(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
| inline void getfat()
{
int lok=1;
int i;
for(i=1;i<=n-2;i++) d[a[i]]++;
a[n-1]=n;
for(i=1;i<=n-2;i++)
{
while(d[lok]) lok++;
f[lok]=a[i];
vis[lok]=1;
while(i<n&&!--d[a[i]]&&lok>=a[i])
{
i++;
f[a[i-1]]=a[i];
}
lok++;
}
int ans=0;
for(i=1;i<=n-1;i++) ans^=(i*f[i]);
cout<<ans<<endl;
}
|
然后接着想你就会发现，这东西不仅可以用来做prufer还原f，同理还可以用来构造prufer
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
| inline void getprufer()
{
int i;
int lok=1;
for(i=1;i<=n-1;i++) d[a[i]]++;
for(i=1;i<=n-2;i++)
{
while(d[lok]) lok++;
prufer[i]=a[lok];
while(i<n-1&&!--d[prufer[i]]&&prufer[i]<lok)
{
i++;
prufer[i]=a[prufer[i-1]];
}
lok++;
}
int ans=0;
for(i=1;i<=n-2;i++) ans^=(i*prufer[i]);
cout<<ans<<endl;
}
s
|
