乱写过完

编译通过...

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

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

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

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

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

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

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

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

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

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

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

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

一开始编什么都不知道 连汇都没 竟然70

后来S-->T T-->S 加oo的边 原点出弧设为M 便AC了

不到50行，膜拜CQF神牛和楼下的傻子

点费用我设的-20000也过了

（太小会有溢出的危险，虽然楼下那个半秃也AC了）

我他M一开始没加相反边，然后又把容量m打成了n，最近太没感了……

编译通过...

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

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

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

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

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

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

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

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

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

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

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

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

我用的是普通的费用流

拆点，建超级源，超级汇

点内容量Vi，费用-1000000(一会会说明为什么) （1）

点之间容量无穷大，费用是坐飞机的费用

超级源也拆开，点之间容量m，费用0，点到原来的点容量无穷大，费用0

超级汇也这样处理

如果（1）处费用是0，那流就直接从源流出来到汇了

为了“尽量引着流往点里钻”，把点内费用设成-1000000

由于最大流肯定是m，最小费用流肯定要尽量流过点，这样每个点刚好流满

最后还要减去本来不应该加的那些-1000000

这是我自己想的方法，不知道对不对，反正是AC了,理论上那个-1000000好像还要再小点的

一开始全TLE，后来发现SPFA忘用循环队列了……

编译通过...

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

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

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

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

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

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

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

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

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

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

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

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

哈哈~~我也来顶你们一下

编译通过...

郁闷我的好慢啊……

编译通过...

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

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

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

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

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

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

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

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

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

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

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

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

上下界费用流

一次ac!

(就是有点慢...)

编译通过...

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

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

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

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

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

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

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

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

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

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

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

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

模型很巧妙~~

要拆点的网络流~~~~

...............

感觉上是一道要想几天的题目

错了……

哈哈哈,本弱智ACCEPTED

编译通过...

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

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

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

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

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

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

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

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

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

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

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

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

用到有容量下界的最小费用流,时间复杂度最坏估计约O(n*m*M)(n=2*N+5,m

如下所说，最小费用最大流（我的要拆点）

我算法的时间复杂度是O(M*N^3)，xiaomengxian算法的时间复杂度是O(M*N^4)。

vijos上他程序的速度比我的还快，强。。。(但在他机子上测，我的程序比他的快一倍)

CQF..我都不敢做了..

最小费用最大流..模型很明显..

惨了..模型不明显了...

ER..CQF大牛出的题目啊..

绿色的云的算法～～
只想到了前一半，加以个直接出发的节点很妙。
```c++
#include<cstdio>
#include<vector>
#include<cstring>
#include<algorithm>
#include<queue>
using namespace std;
const int maxn = 500;
const int INF = 2147483647;

struct Ed
{
int from,to,cap,flow,cost;
Ed(int a=0,int b=0,int c=0,int d=0,int e=0) : from(a), to(b), cap(c), flow(d), cost(e) {};
};

int n,m;
vector<int> G[maxn];
vector<Ed> edges;

inline void add_edge(int from,int to,int cap,int cost)
{
edges.push_back(Ed(from,to,cap,0,cost));
edges.push_back(Ed(to,from,0,0,-1*cost));
int k=edges.size();
G[from].push_back(k-2);
G[to].push_back(k-1);
}

int Bellmen_ford()
{
int cost=0,p[maxn],dis[maxn],a[maxn];
bool inq[maxn];
queue<int> q;

int s=0,t=2*n+1;
while(true)
{
memset(inq,0,sizeof(inq));
memset(dis,-1,sizeof(dis));
q.push(s);
inq[s]=true;
a[s]=INF;
dis[s]=0;

while(!q.empty())
{
int now=q.front();q.pop();
inq[now]=false;

for(int i=0;i<(int)G[now].size();i++)
{
Ed &e=edges[G[now][i]];
if(e.cap>e.flow&&(dis[e.to]==-1||dis[e.to]>dis[now]+e.cost))
{
dis[e.to]=dis[now]+e.cost;
a[e.to]=min(a[now],e.cap-e.flow);
p[e.to]=G[now][i];
if(inq[e.to]==false) {q.push(e.to);inq[e.to]=true;}
}
}
}

if(dis[t]==-1) return cost;

cost+=a[t]*dis[t];
int x=t;
while(x!=s)
{
edges[p[x]].flow+=a[t];
edges[p[x]^1].flow-=a[t];
x=edges[p[x]].from;
}
}
}

int main()
{
scanf("%d%d",&n,&m);
add_edge(0,2*n+2,m,0);
for(int i=1;i<=n;i++)
{
int v;
scanf("%d",&v);
add_edge(0,i,v,0);
add_edge(i+n,2*n+1,v,0);
add_edge(2*n+2,i+n,INF,0);
}
for(int i=1;i<=n;i++)
for(int j=i+1;j<=n;j++)
{
int c;
scanf("%d",&c);
if(c!=-1) add_edge(i,j+n,INF,c);
}

int ans=Bellmen_ford();
printf("%d\n",ans);
return 0;
}

/* Accepted, time = 324 ms, mem = 1224 KiB, score = 100 2016年6月21日星期二 */
```

借鉴了绿色的云的题解
```c++
#include<iostream>
#include<fstream>
#include<cstring>
#include<queue>
#include<vector>
using namespace std;

const int maxm = 500;
const int maxn = 500;
const int inf = 0x7fffffff;

struct edge {
int from, to, cap, flow, cost;
};

vector<edge> edges;
vector<int> g[maxn];
int s, t, k;
int n, m;
int v[maxn];
int a[maxn];
int d[maxn];
int p[maxn];
bool inq[maxn];

void add (int from, int to, int cap, int cost) {
int m = edges.size();
edges.push_back (edge {from, to, cap, 0, cost});
edges.push_back (edge {to, from, 0, 0, -cost});
g[from].push_back(m);
g[to].push_back(m + 1);
}

bool bellmanford (int& flow, int& cost) {
for (int i = 0; i <= 3 * n; i++) { d[i] = inf; inq[i] = false;}
d[s] = 0; a[s] = inf; inq[s] = true; p[s] = 0;
queue<int> q;
q.push (s);
while (!q.empty()) {
int x = q.front(); q.pop();
inq[x] = false;
for (int i = 0; i < g[x].size(); i++) {
edge& e = edges[g[x][i]];
if (e.cap > e.flow && d[e.to] > d[x] + e.cost) {
d[e.to] = d[x] + e.cost;
p[e.to] = g[x][i];
a[e.to] = min (a[x], e.cap - e.flow);
if (!inq[e.to]) {
inq[e.to] = true;
q.push(e.to);
}
}
}
}
if (d[t] == inf) return false;
flow += a[t];
cost += a[t] * d[t];
int u = t;
while (u != s) {
edges[p[u]].flow += a[t];
edges[p[u]^1].flow -= a[t];
u = edges[p[u]].from;
}
return true;
}

int mincost () {
int cost = 0; int flow = 0;
while (bellmanford (flow, cost));
return cost;
}

int main ()
{
// ifstream cin("in.txt");
cin >> n >> m;
s = 2 * n + 1;
t = 2 * n + 2;
k = 2 * n + 3;
for (int i = 1; i <= n; i++) cin >> v[i];
add (s, k, m, 0);
int l;
for (int i = 1; i <= n; i++) {
add (k, i + n, inf, 0);
add (s, i, v[i], 0);
add (n + i, t, v[i], 0);
for (int j = i + 1; j <= n; j++) {
cin >> l;
if (l != -1) {
add (i, j + n, inf, l);
}
}
}
cout << mincost();
return 0;
}
```

费用流模型很明显……只不过没想到CJF天牛的钻点思想……估计加上SLF优化后会很强大！

{---|---|---|---|---|我是邪恶的分割线---|---|---|---|--}

编译通过...

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

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

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

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

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

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

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

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

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

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

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

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

搞定此题……其实很水……我前两次没刷过……因为216（数据开小了）