题目：https://www.luogu.org/problemnew/show/P4013
网络流。有无限制就是容量为1还是INF。
发现ek算法难道不能规定源点拥有的流量？
复制代码
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<iostream> #include<cstdio> #include<cstring> #include<queue> using namespace std; typedef long long ll; const int N=1205,INF=705; int n,m,head[N],xnt=1,incf[N],pre[N],t; ll dis[N],ans; bool in[N]; struct Edge{ int next,from,to,cap; ll w; Edge(int n=0,int f=0,int t=0,int c=0,ll w=0):next(n),from(f),to(t),cap(c),w(w) {} }edge[N<<3],sid[N<<3]; bool spfa() { queue<int> q; memset(dis,-2,sizeof dis); memset(pre,0,sizeof pre); q.push(0);in[0]=1;dis[0]=0;incf[0]=INF; while(q.size()) { int k=q.front();q.pop();in[k]=0; // printf("k=%dn",k); for(int i=head[k],v;i;i=sid[i].next) { // printf(" (to=%d)n",sid[i].to); if(sid[i].cap&&dis[k]+sid[i].w>dis[v=sid[i].to]) { // printf(" v=%dn",v); dis[v]=dis[k]+sid[i].w; incf[v]=min(incf[k],sid[i].cap); pre[v]=i; if(!in[v])q.push(v),in[v]=1; } } } return pre[t]; } void ek() { // printf("(%d)",incf[t]); ans+=dis[t]*incf[t]; for(int k=pre[t];k;k=pre[sid[k].from]) { sid[k].cap-=incf[t]; sid[k^1].cap+=incf[t]; } } void solve() { while(spfa()) ek(); printf("%lldn",ans); ans=0; } int main() { scanf("%d%d",&m,&n); int num=(m+(m+n-1))*n/2; ll x,bh=0;t=2*num+1; for(int i=1;i<=n;i++) { for(int j=1;j<=m+i-1;j++) { int k=bh+j,u=k-(m+i-2); scanf("%lld",&x); // printf("(k=%d u=%d)n",k,u); edge[++xnt]=Edge(head[k],k,k+num,1,x);head[k]=xnt; edge[++xnt]=Edge(head[k+num],k+num,k,0,-x);head[k+num]=xnt; if(i==1) { edge[++xnt]=Edge(head[0],0,k,1,0);head[0]=xnt; edge[++xnt]=Edge(head[k],k,0,0,0);head[k]=xnt; continue; } if(i==n) { edge[++xnt]=Edge(head[k+num],k+num,t,INF,0);head[k+num]=xnt; edge[++xnt]=Edge(head[t],t,k+num,0,0);head[t]=xnt; } if(j!=m+i-1) { edge[++xnt]=Edge(head[u+num],u+num,k,1,0);head[u+num]=xnt; edge[++xnt]=Edge(head[k],k,u+num,0,0);head[k]=xnt; } if(j!=1) { edge[++xnt]=Edge(head[u-1+num],u-1+num,k,1,0);head[u-1+num]=xnt; edge[++xnt]=Edge(head[k],k,u-1+num,0,0);head[k]=xnt; } } bh+=m+i-1; } memcpy(sid,edge,sizeof edge); solve(); memcpy(sid,edge,sizeof edge); for(int i=2;i<=xnt;i++) if(sid[i].w&&sid[i].cap)sid[i].cap=INF; solve(); memcpy(sid,edge,sizeof edge); for(int i=2;i<=xnt;i++) if(sid[i].cap&&sid[i].to>m)sid[i].cap=INF; solve(); return 0; }
转载于:https://www.cnblogs.com/Narh/p/8781611.html
最后
以上就是文静鲜花最近收集整理的关于洛谷4013数字梯形的全部内容，更多相关洛谷4013数字梯形内容请搜索靠谱客的其他文章。
本图文内容来源于网友提供，作为学习参考使用，或来自网络收集整理，版权属于原作者所有。
发表评论 取消回复