题解 - Vijos

3

绿色的云 LV 10 @ 2013-12-29 14:57:45

P121380人环游世界非上下界费用流解法：
首先把每个点拆成两个，分别表示来源跟去向，用wi,ui表示，那么由于每个点会有vi个人经过，那么连边(S,wi,vi,0),(ui,T,vi,0)（(u,v,f,c)表示从u连边到v，流量f，费用c），那么对于每条费用为pi的航线(s,t)就有连边(ws,ut,inf,pi),又由于有些人可以直接在某个城市出发，那么另加一个点k，连边(S,k,m,0),对于每个城市i,连边(k,ui,inf,0)，然后跑一次最小费用最大流，那么mincost就是答案了。。。（这算是经典模型了吧。。。）
zkw费用流写渣了。。。好慢好慢：

编译成功

测试数据 #0: Accepted, time = 78 ms, mem = 952 KiB, score = 10
测试数据 #1: Accepted, time = 78 ms, mem = 956 KiB, score = 10
测试数据 #2: Accepted, time = 0 ms, mem = 504 KiB, score = 10
测试数据 #3: Accepted, time = 78 ms, mem = 952 KiB, score = 10
测试数据 #4: Accepted, time = 0 ms, mem = 508 KiB, score = 10
测试数据 #5: Accepted, time = 62 ms, mem = 956 KiB, score = 10
测试数据 #6: Accepted, time = 93 ms, mem = 952 KiB, score = 10
测试数据 #7: Accepted, time = 109 ms, mem = 956 KiB, score = 10
测试数据 #8: Accepted, time = 109 ms, mem = 952 KiB, score = 10
测试数据 #9: Accepted, time = 93 ms, mem = 952 KiB, score = 10
Accepted, time = 700 ms, mem = 956 KiB, score = 100

#include <cstdio>
#include <algorithm>
#include <cstring>

using namespace std ;

#define MAXN 210
#define inf 0x7fffffff

struct network {

int S , T ;

struct edge {
edge *next , *pair ;
int t , f , c ;
} *head[ MAXN ] ;

network( ) {
memset( head , 0 , sizeof( head ) ) ;
}

void Add( int s , int t , int f , int c ) {
edge *p = new( edge ) ;
p -> t = t , p -> f = f , p -> c = c , p -> next = head[ s ] ;
head[ s ] = p ;
}

void AddEdge( int s , int t , int f , int c ) {
Add( s , t , f , c ) , Add( t , s , 0 , - c ) ;
head[ s ] -> pair = head[ t ] , head[ t ] -> pair = head[ s ] ;
}

int dist[ MAXN ] , slack[ MAXN ] , cost ;
bool f[ MAXN ] ;

int aug( int v , int flow ) {
if ( v == T ) {
cost += flow * dist[ S ] ;
return flow ;
}
f[ v ] = true ;
int rec = 0 ;
for ( edge *p = head[ v ] ; p ; p = p -> next ) if ( p -> f && ! f[ p -> t ] ) {
if ( dist[ v ] == dist[ p -> t ] + p -> c ) {
int ret = aug( p -> t , min( flow - rec , p -> f ) ) ;
p -> f -= ret , p -> pair -> f += ret ;
if ( ( rec += ret ) == flow ) return flow ;
} else slack[ p -> t ] = min( slack[ p -> t ] , dist[ p -> t ] + p -> c - dist[ v ] ) ;
}
return rec ;
}

bool relabel( ) {
int delta = inf ;
for ( int i = 0 ; i ++ < T ; ) if ( ! f[ i ] ) delta = min( delta , slack[ i ] ) ;
if ( delta == inf ) return false ;
for ( int i = 0 ; i ++ < T ; ) if ( f[ i ] ) dist[ i ] += delta ;
return true ;
}

int costflow( ) {
cost = 0 ;
memset( dist , 0 , sizeof( dist ) ) ;
do {
for ( int i = 0 ; i ++ < T ; ) slack[ i ] = inf ;
do {
memset( f , false , sizeof( f ) ) ;
} while ( aug( S , inf ) ) ;
} while ( relabel( ) ) ;
return cost ;
}

} net ;

int n , m , v[ MAXN ][ 2 ] , V = 0 ;

int main( ) {
scanf( "%d%d" , &n , &m ) ;
for ( int i = 0 ; i ++ < n ; ) v[ i ][ 0 ] = ++ V , v[ i ][ 1 ] = ++ V ;
++ V ; net.S = ++ V ; net.T = ++ V ;
net.AddEdge( net.S , V - 2 , m , 0 ) ;
for ( int i = 0 ; i ++ < n ; ) {
int x ; scanf( "%d" , &x ) ;
net.AddEdge( net.S , v[ i ][ 0 ] , x , 0 ) ;
net.AddEdge( v[ i ][ 1 ] , net.T , x , 0 ) ;
net.AddEdge( V - 2 , v[ i ][ 1 ] , inf , 0 ) ;
}
for ( int i = 0 ; i ++ < n - 1 ; ) {
for ( int j = i ; j ++ < n ; ) {
int x ; scanf( "%d" , &x ) ;
if ( x != -1 ) {
net.AddEdge( v[ i ][ 0 ] , v[ j ][ 1 ] , inf , x ) ;
}
}
}
printf( "%d\n" , net.costflow( ) ) ;
return 0 ;
}

1

Sky1231 (sky1231) LV 10 @ 2017-07-15 16:51:56

#include <cmath>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <iomanip>
#include <algorithm>
#include <vector>
#include <deque>
#include <limits>
#include <string>
#include <sstream>
using namespace std;

const int oo_min=0xcfcfcfcf,oo_max=0x3f3f3f3f;

int n,m;
vector<int> f;
vector<int> e;
vector<int> u;
vector<int> pre;
vector<int> vis;
vector<vector<int> > c;
vector<vector<int> > p;
vector<vector<int> > ce;
vector<vector<int> > cw;
deque<int> q;

void add_edge_1(int x,int y,int c_v,int 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);
}

int bfs_1(int s,int t,int *flow,int *cost)
{
    f.resize(0);
    f.resize(cw.size(),0);
    f[s]=oo_max;
    e.resize(0);
    e.resize(cw.size(),-1);
    u.resize(0);
    u.resize(cw.size(),oo_max);
    u[s]=0;
    pre.resize(0);
    pre.resize(cw.size(),-1);
    pre[s]=s;
    vis.resize(0);
    vis.resize(cw.size(),0);
    for (q.resize(0),vis[s]=1,q.push_back(s);(!q.empty());vis[q.front()]=0,q.pop_front())
    {
        int now=q.front();
        for (int i=0;i<cw[now].size();i++)
            if (c[now][i]&&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_1(int s,int t,int *flow,int *cost)
{
    int temp_flow,temp_cost;
    while (bfs_1(s,t,&temp_flow,&temp_cost))
    {
        for (int 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;
        (*cost)+=(temp_flow*temp_cost);
    }
}

int main()
{
    
    while (~scanf("%d%d",&n,&m))
    {
        cw.resize(0);
        cw.resize(2*n+3);
        ce.resize(0);
        ce.resize(cw.size());
        c.resize(0);
        c.resize(cw.size());
        p.resize(0);
        p.resize(cw.size());
        for (int i=0;i<cw.size();i++)
        {
            cw[i].resize(0);
            ce[i].resize(0);
            c[i].resize(0);
            p[i].resize(0);
        }
        add_edge_1(0,c.size()-2,m,0);
        for (int i=1;i<=n;i++)
        {
            int v;
            scanf("%d",&v);
            add_edge_1(0,i,v,0);
            add_edge_1(i+n,cw.size()-1,v,0);
            add_edge_1(cw.size()-2,i+n,oo_max,0);
        }
        for (int i=1;i<=n-1;i++)
            for (int j=1;j<=n-i;j++)
            {
                int cost;
                scanf("%d",&cost);
                if (cost!=-1)
                    add_edge_1(i,i+j+n,oo_max,cost);
            }
        int ans_flow=0,ans_cost=0;
        min_cost_max_flow_1(0,c.size()-1,&ans_flow,&ans_cost);
        printf("%d\n",ans_cost);
    }
}

sky1231 @ 2017-07-15 17:13:03

状态耗时内存占用
#1 Accepted 11ms 636.0KiB
#2 Accepted 15ms 512.0KiB
#3 Accepted 3ms 324.0KiB
#4 Accepted 22ms 600.0KiB
#5 Accepted 4ms 256.0KiB
#6 Accepted 22ms 512.0KiB
#7 Accepted 24ms 512.0KiB
#8 Accepted 41ms 724.0KiB
#9 Accepted 54ms 612.0KiB
#10 Accepted 57ms 616.0KiB
分数 100
总耗时 257ms
峰值内存 724.0KiB

0

root (zhuqirui123) LV 10 @ 2023-10-07 23:25:16

/********************************************************
备注：
********************************************************/
#include <iostream>
#include <iomanip>
#include <cmath>
#include <cstring>
#include <algorithm>
#include <cstdio>
using namespace std;
#define LL long long
#define MAXM 3010
#define MAXN 3010
const int N =1e5+10;
const int INF =0x3f3f3f3f;
int main ()
{
int a,b;
cin>>a>>b;
cout<<a+b;
return 0;
}

0

Antinomy LV 8 @ 2017-01-04 14:38:55

测试数据 #0: Accepted, time = 31 ms, mem = 1240 KiB, score = 10
测试数据 #1: Accepted, time = 31 ms, mem = 1244 KiB, score = 10
测试数据 #2: Accepted, time = 0 ms, mem = 668 KiB, score = 10
测试数据 #3: Accepted, time = 31 ms, mem = 1240 KiB, score = 10
测试数据 #4: Accepted, time = 0 ms, mem = 668 KiB, score = 10
测试数据 #5: Accepted, time = 46 ms, mem = 1240 KiB, score = 10
测试数据 #6: Accepted, time = 46 ms, mem = 1240 KiB, score = 10
测试数据 #7: Accepted, time = 62 ms, mem = 1240 KiB, score = 10
测试数据 #8: Accepted, time = 93 ms, mem = 1240 KiB, score = 10
测试数据 #9: Accepted, time = 93 ms, mem = 1240 KiB, score = 10
Accepted, time = 433 ms, mem = 1244 KiB, score = 100

借用了楼下绿色的云的建图方法，对这些建模的方法的理解越来越快了，果然在草稿纸上画一下很容易理解啊。。
要加油，争取自己也能想出这样的建模方法

代码
```c++
#include<iostream>
#include<iomanip>
#include<cstring>
#include<vector>
#include<sstream>
#include<algorithm>
#include<string>
#include<cstdio>
#include<math.h>
#include<map>
#include<cctype>
#include<queue>
#include<functional>
#include<set>
#define Mem(a,b) memset((a),(b),sizeof((a)))
#define Sy system("pause")
const int maxn = 1000;
const int INF = 0x3f3f3f;
using namespace std;

struct MCMF{

struct Edge
{
int from, to, cap, flow, cost;
Edge(int a, int b, int c, int d, int e) :from(a), to(b), cap(c), flow(d), cost(e) {}
Edge(){}
};
int n, m;
vector<Edge> edges;
vector<int> G[maxn];
int inq[maxn], d[maxn], p[maxn], a[maxn];

void init(int n){
this->n = n;
for (int i = 0; i < n; i += 1)G[i].clear(); edges.clear();
}

void AddEdge(int from, int to, int cap, int cost){
edges.push_back(Edge(from, to, cap, 0, cost));
edges.push_back(Edge(to, from, 0, 0, -cost));
m = edges.size();
G[from].push_back(m - 2);
G[to].push_back(m - 1);
}

bool BellmanFord(int s, int t, int & flow, int & cost){
for (int i = 0; i < n; i += 1) d[i] = INF;
memset(inq, 0, sizeof(inq));
d[s] = 0; inq[s] = 1; p[s] = 0; a[s] = INF;
queue<int> Q;
Q.push(s);
while (!Q.empty())
{
int u = Q.front(); Q.pop();
inq[u] = 0;
for (int i = 0; i < G[u].size(); i += 1){
Edge & e = edges[G[u][i]];
if (e.cap > e.flow && d[e.to] > d[u] + e.cost){
d[e.to] = d[u] + e.cost;
p[e.to] = G[u][i];
a[e.to] = min(a[u], e.cap - e.flow);
if (!inq[e.to]){
Q.push(e.to); inq[e.to] = 1;
}
}
}
}
if (d[t] == INF) return false;
flow += a[t];
cost += d[t] * a[t];

for (int u = t; u != s; u = edges[p[u]].from){
edges[p[u]].flow += a[t];
edges[p[u] ^ 1].flow -= a[t];
}
return true;
}

int MinCostMaxFlow(int s, int t, int & cost){
int flow = 0; cost = 0;
while (BellmanFord(s, t, flow, cost));
return flow;
}
};

/*
S:0 Wi:[1,n] Ui:[n+1,2n] k:[2n+1] T[2n+2]
*/

int main(){
MCMF D;
int n, m;
scanf("%d %d", &n, &m);
int s = 0, t = 2 * n + 2, k = 2 * n + 1;
int tmp;
D.init(2 * n + 3);
D.AddEdge(s, k, m, 0);
for (int i = 1; i <= n; i += 1){
scanf("%d", &tmp);
D.AddEdge(s, i, tmp, 0);
D.AddEdge(i + n, t, tmp, 0);
D.AddEdge(k, i + n, INF, 0);
}
for (int i = 1; i < n; i += 1){
for (int j = i + 1; j <= n; j += 1){
scanf("%d", &tmp);
if (tmp != -1) D.AddEdge(i, j + n, INF, tmp);
}
}

int ans; D.MinCostMaxFlow(s, t, ans);

printf("%d\n", ans);

//Sy;
return 0;
}
```

0

freefood LV 10 @ 2014-05-19 21:27:46

按某云神的方法建图就可以了Orz，第一次用zkw，好快……
http://hi.baidu.com/macaulish64/item/7137993446fc99e9382ffa73
测试数据 #0: Accepted, time = 62 ms, mem = 3456 KiB, score = 10
测试数据 #1: Accepted, time = 78 ms, mem = 3452 KiB, score = 10
测试数据 #2: Accepted, time = 7 ms, mem = 3456 KiB, score = 10
测试数据 #3: Accepted, time = 62 ms, mem = 3456 KiB, score = 10
测试数据 #4: Accepted, time = 15 ms, mem = 3456 KiB, score = 10
测试数据 #5: Accepted, time = 62 ms, mem = 3452 KiB, score = 10
测试数据 #6: Accepted, time = 78 ms, mem = 3456 KiB, score = 10
测试数据 #7: Accepted, time = 109 ms, mem = 3456 KiB, score = 10
测试数据 #8: Accepted, time = 109 ms, mem = 3456 KiB, score = 10
测试数据 #9: Accepted, time = 93 ms, mem = 3452 KiB, score = 10

0

yanyao1314 LV 9 @ 2013-09-02 19:36:29

学习了。，。

0

叶德铭 LV 9 @ 2010-04-06 20:46:35

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

有点慢

那个点内的反向弧是费用20000（不是-20000），弄错了......

0

xuketian LV 9 @ 2010-03-14 22:00:38

很经典的模型 ~

0

mike_nzk LV 10 @ 2009-09-26 12:13:12

杯具，为了个SX错误WA了2次。

0

boyzkk LV 10 @ 2009-07-23 08:49:16

编译通过...

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

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

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

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

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

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

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

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

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

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

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

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

第一次。。。输出了调试的东东

膜拜CJF神牛。

0

lijian3256 LV 10 @ 2009-07-22 18:16:08

..顽强的用了 AC 。。

0

retsamio LV 8 @ 2009-07-21 19:53:11

SPFA用SLF就能0ms了！（注意要写

0

Cksj LV 8 @ 2009-06-29 02:01:33

编译通过...

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

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

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

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

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

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

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

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

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

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

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

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

SLF 王道！！！

膜拜 CJF 天牛！！！

最开始跑出来的一直是零，后来发现在添加两个国家之间的那个弧我把费用打成了零。。。最近没状态。。。

0

src250 LV 10 @ 2009-06-20 08:15:18

感谢陈健飞神牛的题解！

将点的费用设为一个很小的数，这方法太神了！

第100人AC，庆祝一下！

0

oimaster LV 10 @ 2009-06-11 21:59:36

zkw费用流就是快……

0msAC了！

0

michaelyu LV 8 @ 2009-04-13 16:22:01

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

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

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

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

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

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

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

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

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

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

0

voyagec2 LV 10 @ 2009-04-03 20:57:52

编译通过...

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

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

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

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

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

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

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

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

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

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

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

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

我太菜了,现在才会费用流,不过A了就好

0

k103701 LV 10 @ 2009-03-26 19:06:21

没加优化前

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

加了一个小优化后

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

强烈在spfa时队首队尾两端插入，效率明摆着

而且只不过加了一行

0

pzy3303 LV 10 @ 2009-03-12 20:54:05

注意。。每个节点访问的次数是固定的。且一定有M个人出去访问

0

curimit LV 10 @ 2009-02-17 21:58:46

太好了！！！

一遍编完没有调试就过了！！！

题解

41 条题解

80人环游世界

信息

状态

开发

支持

题解

41 条题解

80人环游世界

信息

状态

开发

支持

还没有账户？

登录