2020-2021:teams:i_dont_know_png:potassium:linear_programming

差别

这里会显示出您选择的修订版和当前版本之间的差别。

到此差别页面的链接

--- 2020-2021:teams:i_dont_know_png:potassium:linear_programming [2020/05/24 18:50]
potassium [练习题]
+++ 2020-2021:teams:i_dont_know_png:potassium:linear_programming [2020/05/24 19:59] (当前版本)
potassium
@@ 行 31: / 行 31: @@
 ==== 模板题 ====
-[[https://www.luogu.com.cn/problem/P3980|NOI 2008 志愿者招募]] [[https://byvoid.com/zhs/blog/noi-2008-employee/|题解]]
-==== 练习题 ====
 [[https://codeforces.com/gym/101190|NEERC 2016 D. Delight for a Cat]]
@@ 行 190: / 行 186: @@
 </hidden>
+==== 练习题 ====
+[[https://www.luogu.com.cn/problem/P3980|NOI 2008 志愿者招募]] [[https://byvoid.com/zhs/blog/noi-2008-employee/|题解]]
+**题意**：有 $n$ 天， $m$ 种工作时间为 $[s_i,t_i]$ ，工资为 $v_i$ 的志愿者，每个时间点有志愿者个数要求，求最小花费。
+**题解**：抽象出来每个方程的样子，发现对于每个 $x_i$ ，差分之后连的是一条 $s_i\rightarrow t_i+1$ 的边，松弛变量和常数与上题类似。
+<hidden 参考代码>
+<code:cpp>
+#include<cstdio>
+#include<algorithm>
+#include<queue>
+#include<map>
+#include<cstring>
+#include<cmath>
+#include<cstdlib>
+#include<set>
+#include<unordered_map>
+#include<vector>
+typedef long long ll;
+using namespace std;
+#define pii pair<int,int>
+#define pb push_back
+#define mp make_pair
+#define fi first
+#define se second
+#define N 5002
+struct Edge{
+	int e,n;
+	ll l,c;
+}e[20*N];
+struct Pre{
+	int pre,edge;
+}pre[N];
+int hd[N],vis[N],cnt=1,s,t;
+ll maxflow,mincost,dis[N],flow[N];
+void add(int a,int b,ll l,ll c){
+	e[++cnt].e=b;
+	e[cnt].l=l;
+	e[cnt].c=c;
+	e[cnt].n=hd[a];
+	hd[a]=cnt;
+}
+void add2(int a,int b,ll l,ll c){
+	//printf("%d %d %d %d\n",a,b,l,c);
+	add(a,b,l,c);
+	add(b,a,0,-c);
+}
+queue<int>Q;
+int spfa(){
+	memset(dis,0x7f,sizeof(dis));
+	memset(flow,0x7f,sizeof(flow));
+	memset(vis,0,sizeof(vis));
+	while(!Q.empty())Q.pop();
+	int i,top,q;
+	Q.push(s);vis[s]=1;dis[s]=0;pre[t].pre=0;
+	while(!Q.empty()){
+		top=Q.front();
+		Q.pop();
+		vis[top]=0;
+		for(i=hd[top];i;i=e[i].n){
+			q=e[i].e;
+			if(e[i].l&&dis[q]>dis[top]+e[i].c){
+				dis[q]=dis[top]+e[i].c;
+				pre[q].pre=top;
+				pre[q].edge=i;
+				flow[q]=min(flow[top],e[i].l);
+				if(!vis[q]){
+					vis[q]=1;
+					Q.push(q);
+				}
+			}
+		}
+	}
+	return pre[t].pre;
+}
+void ek(){
+	int i;
+	while(spfa()){
+		maxflow+=flow[t];
+		mincost+=flow[t]*dis[t];
+		for(i=t;i!=s;i=pre[i].pre){
+			e[pre[i].edge].l-=flow[t];
+			e[pre[i].edge^1].l+=flow[t];
+		}
+	}
+}
+int a[N];
+int main(){
+	int i,n,m,ms,me;
+	scanf("%d%d",&n,&m);
+	for(i=1;i<=n;i++)scanf("%d",&a[i]);
+	s=n+2;t=s+1;
+	for(i=0;i<m;i++){
+		int l,r,v;
+		scanf("%d%d%d",&l,&r,&v);
+		add2(l,r+1,1e18,v);
+	}
+	for(i=1;i<=n;i++)add2(i+1,i,1e18,0);
+	add2(s,1,a[1],0);
+	for(i=2;i<=n;i++){
+		if(a[i]-a[i-1]>=0)add2(s,i,a[i]-a[i-1],0);
+		else add2(i,t,a[i-1]-a[i],0);
+	}
+	add2(n+1,t,a[n],0);
+	ek();
+	printf("%lld\n",mincost);
+	return 0;
+}
+</code>
+</hidden>

2020-2021/teams/i_dont_know_png/potassium/linear_programming.1590317422.txt.gz · 最后更改: 2020/05/24 18:50 由 potassium