# 30 条题解

• @ 2017-07-13 15:26:23
``````#include <cmath>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <iomanip>
#include <iostream>
#include <algorithm>
#include <vector>
#include <deque>
#include <set>
#include <limits>
#include <string>
#include <sstream>
using namespace std;

namespace dts
{
typedef long long ll;

double oo_min=(numeric_limits<double>::min)(),oo_max=(numeric_limits<double>::max)();

struct network_flows
{
vector<ll> e;
vector<ll> pre;
vector<ll> vis;
vector<vector<ll> > cw;
vector<vector<ll> > ce;
vector<double> f;
vector<double> u;
vector<vector<double> > c;
vector<vector<double> > p;
deque<ll> q;

void clear_flow()
{
e.clear();
pre.clear();
vis.clear();
f.clear();
u.clear();
}

void clear_edge()
{
clear_flow();
cw.clear();
ce.clear();
c.clear();
p.clear();
}

ll size()
{
return cw.size();
}

void set_size(ll size_v)
{
clear_edge();
cw.resize(size_v);
ce.resize(size());
c.resize(size());
p.resize(size());
}

void add_edge(ll x,ll y,double c_v,double p_v)
{
cw[x].push_back(y);
c[x].push_back(c_v);
p[x].push_back(p_v);
ce[y].push_back(cw[x].size()-1);
cw[y].push_back(x);
c[y].push_back(0);
p[y].push_back(-p_v);
ce[x].push_back(cw[y].size()-1);
}

void prepare(ll s,ll t)
{
clear_flow();
f.resize(size(),0);
f[s]=oo_max;
e.resize(size(),-1);
u.resize(size(),oo_max);
u[s]=0;
pre.resize(size(),-1);
pre[s]=s;
vis.resize(size(),0);
}

ll bfs(ll s,ll t,double &flow,double &cost)
{
prepare(s,t);
for (q.clear(),vis[s]=1,q.push_back(s);!q.empty();vis[q.front()]=0,q.pop_front())
{
ll now=q.front();
for (ll i=0;i<cw[now].size();i++)
if (c[now][i]>0&&u[now]+p[now][i]<u[cw[now][i]])
{
f[cw[now][i]]=min(c[now][i],f[now]);
e[cw[now][i]]=i;
u[cw[now][i]]=u[now]+p[now][i];
pre[cw[now][i]]=now;
if (vis[cw[now][i]]==0)
vis[cw[now][i]]=1,q.push_back(cw[now][i]);
}
}
flow=f[t];
cost=u[t];
return (pre[t]!=-1);
}

void min_cost_max_flow(ll s,ll t,ll typ,double &flow,double &cost)
{
double temp_flow,temp_cost;
while (bfs(s,t,temp_flow,temp_cost))
{
for (ll i=t;i!=s;i=pre[i])
c[pre[i]][e[i]]-=temp_flow,c[i][ce[pre[i]][e[i]]]+=temp_flow;
flow+=temp_flow;
if (typ==0)
cost+=temp_cost;
else if (typ==1)
cost+=(temp_flow*temp_cost);
}
}
}net;

ll n,m,t;
vector<double> a;

void main()
{
while (~scanf("%lld%lld%lld",&n,&m,&t))
{
a.clear();
a.resize(n+1,0);
for (int i=1;i<=n;i++)
scanf("%lf",&a[i]);
net.set_size(n-m+4);
for (int i=1;i<=m;i++)
for (int i=n-m+1;i<=n;i++)
for (int i=m+1;i<=n-m;i++)
for (int i=1;i<=n-m+1;i++)
double ans_flow=0,ans_cost=0;
net.min_cost_max_flow(0,net.size()-1,0,ans_flow,ans_cost);
printf("%.0lf\n",-ans_cost);
}
}
};

int main()
{
dts::main();
}
``````
• @ 2014-10-20 17:03:25

研究了一天终于懂了 参考的是楼下boyzkk大神

下面以N=5，M=2为例
c[1]+c[2]<=k
c[2]+c[3]<=k
c[3]+c[4]<=k
c[4]+c[5]<=k
变换得
c[1]+c[2]+y[1]-k=0
c[2]+c[3]+y[2]-k=0
c[3]+c[4]+y[3]-k=0
c[4]+c[5]+y[4]-k=0

添加0式为空，5式为空
前-后得
c[1]-c[2]+y[1]-k=0
c[3]-c[1]+y[2]-y[1]=0
c[4]-c[2]+y[3]-y[2]=0
c[5]-c[3]+y[4]-y[3]=0
-c[4]-c[5]-y[4]+k=0

对于任意变量，在所有式子中均只出现两次，且一正一负，就像【流量平衡】
于是把正数看做入流，负数看做出流，把每个式子抽象成一个点，连边
比如①中有正C[1]，②中有-C[1]，那么由①向②连一条流量为1，费用为a[1]的边
对于常数K，移向等号右边，那么由S向①式连一条流量为K，费用为0的边
由⑤向T连一条流量为K，费用为0的边
这是我的建图
S=0; tot=n-m+2; T=tot+1;

• @ 2017-07-13 14:32:29

添加0式为空，5式为空
后-前
c[1]+c[2]+y[1]-k=0
c[3]-c[1]+y[2]-y[1]=0
c[4]-c[2]+y[3]-y[2]=0
c[5]-c[3]+y[4]-y[3]=0
-c[4]-c[5]-y[4]+k=0

• @ 2009-08-12 13:57:14

编译通过...

├ 测试数据 01：答案正确... 0ms

├ 测试数据 02：答案正确... 0ms

├ 测试数据 03：答案正确... 0ms

├ 测试数据 04：答案正确... 0ms

├ 测试数据 05：答案正确... 0ms

├ 测试数据 06：答案正确... 0ms

├ 测试数据 07：答案正确... 0ms

├ 测试数据 08：答案正确... 0ms

├ 测试数据 09：答案正确... 0ms

├ 测试数据 10：答案正确... 0ms

---|---|---|---|---|---|---|---|-

Accepted 有效得分：100 有效耗时：0ms

1次AC, 唯一缺憾的是第13次提交...

说一下解法:

c[i]表示第i件物品选与不选, 取值在[0,1].

那么会有原始不等式:

c[1]+c[2]+...+c[m]

• @ 2014-05-30 19:38:32

如果写过Employee的话，只要知道把每个物品当作选或者不选（0或1）来看待就好了
x1+x2+...+xm-y1=k ..然后小心各种样例数据坑人，最好能自己手写一组去试试建边
可以试试 n=13,m=3 k和下面那些数字无所谓，只是为了搞明白怎么建边

• @ 2010-07-16 23:35:02

70行的 朴素 单纯型…………

编译通过...

├ 测试数据 01：答案正确... 852ms

├ 测试数据 02：答案正确... 134ms

├ 测试数据 03：答案正确... 0ms

├ 测试数据 04：运行超时...

├ 测试数据 05：答案正确... 274ms

├ 测试数据 06：运行超时...

├ 测试数据 07：答案正确... 508ms

├ 测试数据 08：运行超时...

├ 测试数据 09：运行超时...

├ 测试数据 10：答案正确... 321ms

---|---|---|---|---|---|---|---|-

Unaccepted 有效得分：60 有效耗时：2089ms

话说我自己机子极限 随机数据是能过的…………

如果不是vag 6k，说不定不优化就能过了……

编译通过...

├ 测试数据 01：答案正确... 321ms

├ 测试数据 02：答案正确... 134ms

├ 测试数据 03：答案正确... 0ms

├ 测试数据 04：答案正确... 0ms

├ 测试数据 05：答案正确... 290ms

├ 测试数据 06：答案正确... 524ms

├ 测试数据 07：答案正确... 25ms

├ 测试数据 08：答案正确... 789ms

├ 测试数据 09：答案正确... 462ms

├ 测试数据 10：答案正确... 0ms

---|---|---|---|---|---|---|---|-

Accepted 有效得分：100 有效耗时：2545ms

加了一行贪心优化之后，依然是vag 6k………

• @ 2010-04-12 20:54:10

弱弱地问一句……什么叫线性规划（DP吗），我只知道这个题是费用流……

• @ 2013-08-23 19:07:50

线性规划跟动态规划不一样，是一种数序方法，高中数学有学的。。
可以费用流解

• @ 2010-04-05 09:34:07

求数据……

有的好心人发我邮箱吧:NWintre@163.com

thx

• @ 2010-04-04 13:49:33

线性规划，重在构图。

• @ 2010-03-15 21:27:47

编译通过...

├ 测试数据 01：答案正确... 0ms

├ 测试数据 02：答案正确... 56ms

├ 测试数据 03：答案正确... 0ms

├ 测试数据 04：答案正确... 0ms

├ 测试数据 05：答案正确... 9ms

├ 测试数据 06：答案正确... 9ms

├ 测试数据 07：答案正确... 0ms

├ 测试数据 08：答案正确... 56ms

├ 测试数据 09：答案正确... 0ms

├ 测试数据 10：答案正确... 0ms

---|---|---|---|---|---|---|---|-

Accepted 有效得分：100 有效耗时：130ms

我是傻X，让这题通过率狂掉………………

模型类似于employee，但建图真的很讨厌…………交了8次，每次建图都不一样……………… - -!

后来发现都是些傻瓜错误，囧。

我就好心的发一下建图方法吧：

for(i=1;i

• @ 2010-03-11 18:52:20

编译通过...

├ 测试数据 01：答案正确... 322ms

├ 测试数据 02：答案正确... 197ms

├ 测试数据 03：答案正确... 0ms

├ 测试数据 04：答案正确... 0ms

├ 测试数据 05：答案正确... 541ms

├ 测试数据 06：答案正确... 197ms

├ 测试数据 07：答案正确... 0ms

├ 测试数据 08：答案正确... 353ms

├ 测试数据 09：答案正确... 228ms

├ 测试数据 10：答案正确... 0ms

---|---|---|---|---|---|---|---|-

Accepted 有效得分：100 有效耗时：1838ms

囧RZ

• @ 2009-09-18 22:47:37

弱弱的我感慨：这题很强大，orz...

• @ 2009-09-13 13:52:38

编译通过...

• @ 2009-09-07 16:47:35

我是一个菜鸟。。。。。

我用搜索与回溯做超时了。

该怎么优化

• @ 2009-09-07 11:32:13

先开始队列尾循环，头忘循环循环，10分。

后来改成循环，Accept。

• @ 2009-08-30 16:23:20

要用链表或者前向星存边,不习惯,不想写了

• @ 2009-08-26 18:37:23

我太沙茶了，边容量是1，搞成maxlongint了

• @ 2009-08-14 11:51:50

谁来罩我把,为什么这题像1525那样构图只有60分.

• @ 2009-08-16 16:49:10

vijos不能添加新题了，voyagec2就覆盖了老题，不好意思啊。

注意题目是绝对值小于1000，如果用zkw费用流必须要先做一次SPFA，否则处理负权边会出问题。

• @ 2009-08-11 13:32:38

谁偷了我的号！！！！！

这个题目不是我加的！！

• @ 2009-08-10 21:07:45

此题建图方法不同会导致时间相差极大。

ufo172849z沙茶建图用spfa不能秒杀。oimaster的神new建图用spfa秒杀。

ID
1499

6

(无)

269

81

30%

2