【codevs1033】蚯蚓的游戏问题-白红宇

【codevs1033】蚯蚓的游戏问题

阅读量：5226 次

发布时间：2019-06-14

本文共 1101 字，大约阅读时间需要 3 分钟。

(题目链接)

题意

　　给出一个梯形的数列，每一个数可以向它左下方和右下方的数走。求从第一行走到最后一行的不重叠的K条路径，使得经过的数的和最大。

Solution

　　很显然的费用流。每个点拆成两个，之间连一条容量为1，费用为数字大小的边。

细节

　　最近写题总是bug百出。。网络流的数组大小真是玄学问题。。

代码

// codevs1033#include
     
      #include
      
       #include
       
        #include
        
         #include
         
          #include
          
           #include
           
            #define LL long long#define inf 2147483640#define Pi acos(-1.0)#define free(a) freopen(a".in","r",stdin),freopen(a".out","w",stdout);using namespace std; const int maxn=10000;struct edge {int from,to,next,w,c;}e[maxn*100];int head[maxn],vis[maxn],p[maxn],f[maxn],dis[maxn];int n,m,es,et,K,cnt=1,a[1000][1000];void link(int u,int v,int w,int c) { e[++cnt]=(edge){u,v,head[u],w,c};head[u]=cnt; e[++cnt]=(edge){v,u,head[v],0,-c};head[v]=cnt;}int SPFA() { queue
            
              q;q.push(es); memset(dis,-1,sizeof(dis)); dis[es]=0;f[es]=inf; while (!q.empty()) { int x=q.front();q.pop(); vis[x]=0; for (int i=head[x];i;i=e[i].next) if (e[i].w && dis[e[i].to]
             
              1 && j>1) link(a[i-1][j-1]+et,u,1,0); if (i>1 && j