P4013 数字梯形问题【网络流24题】

题目描述

给定一个由

梯形的第一行有

分别遵守以下规则：

从梯形的顶至底的
从梯形的顶至底的
从梯形的顶至底的

输入格式

第

输出格式

将按照规则

输入输出样例

输入 #1<button class="copy-btn lfe-form-sz-middle" data-v-370e72e2="" data-v-52f2d52f="" type="button">复制</button>

2 5
2 3
3 4 5
9 10 9 1
1 1 10 1 1
1 1 10 12 1 1

输出 #1<button class="copy-btn lfe-form-sz-middle" data-v-370e72e2="" data-v-52f2d52f="" type="button">复制</button>

66
75
77

说明/提示

$1\leq m,n \leq 201≤m,n≤20$

$思路$

$路径问题，关乎点权$

$以及三种限制条件$

$很容易想到这就是一个最大费用最大流问题$

$已经知道了这是一个最大费用最大流问题$

$就可以着手建图了$

$因为我们要求一个点权和的最大值$

$而网络流是无法解决点权的问题的$

$显然可以把点权转化成边权来做$

$也就是把一个点拆开成 X,Y 两个点$

$这个点的点权就是X、Y之间的边权$

$首先这道题有三个子任务点$

$（一）、路径互不相交$

$显然如果要路径互不相交，也就是既没有公共点，也没有公共边$

$所以，要建出这种限制相当容易，只需要让每个点Xi、Yi之间的流量为1.$

$且每个点和它下方相连的点的边的流量也应该为1$

$这样就可以成功限制每个点每条边都只能用一次这个条件$

$（二）、只能在点处相交$

$换句话说就是一个点能用多次$

$所以其他建图条件可以不变，把对点Xi和Yi之间的限制解除即可$

$（三）、只能在点和边相交$

$此时就已经完全没有限制条件了$

$除了超级源向第一行连边依然是1以外$

$其他所有的边的流量都可以置为无穷$

$具体详见代码$

$CODE$

  1 #include <bits/stdc++.h>
  2 #define dbg(x) cout << #x << "=" << x << endl
  3 #define eps 1e-8
  4 #define pi acos(-1.0)
  5 
  6 using namespace std;
  7 typedef long long LL;
  8 const int maxn = 1e5 +7;
  9 const int inf  = 0x3f3f3f3f;
 10 
 11 int n, m, s, t;
 12 int head[maxn],pre[maxn],inq[maxn],dis[maxn];
 13 int cnt = 1;
 14 int mincost = 0, maxflow = 0;
 15 struct edge {
 16     int u,to,nxt,w,c;
 17 }e[maxn << 1];
 18 
 19 template<class T>inline void read(T &res)
 20 {
 21     char c;T flag=1;
 22     while((c=getchar())<'0'||c>'9')if(c=='-')flag=-1;res=c-'0';
 23     while((c=getchar())>='0'&&c<='9')res=res*10+c-'0';res*=flag;
 24 }
 25 
 26 inline void BuildGraph(int u, int v, int w, int cost)
 27 {
 28     e[++cnt] = (edge){u, v, head[u], w,  cost}, head[u] = cnt;
 29     e[++cnt] = (edge){v, u, head[v], 0, -cost}, head[v] = cnt;///反向边
 30 }
 31 
 32 queue<int> q;
 33 
 34 inline void init() {
 35     memset(head, 0, sizeof(head));
 36     memset(pre, 0, sizeof(pre));
 37     memset(inq, 0, sizeof(inq));
 38     memset(dis, 0, sizeof(dis));
 39     memset(e, 0, sizeof(e));
 40     while(!q.empty()) {
 41         q.pop();
 42     }
 43     mincost = maxflow = 0;
 44     cnt = 1;
 45 }
 46 
 47 bool SPFA(int x)
 48 {
 49     memset(inq, 0, sizeof(inq));
 50     for(int i = s; i <= t; i++) {
 51         dis[i] = inf;
 52     }
 53     q.push(x);
 54     dis[x] = 0;
 55     inq[x] = 1;
 56     while(!q.empty()) {
 57         int u = q.front();
 58         q.pop();
 59         inq[u] = 0;
 60         for(int i = head[u]; i; i = e[i].nxt) {
 61             int v = e[i].to, w = e[i].c;
 62             if(e[i].w > 0) {
 63                 if(dis[u] + w < dis[v]) {
 64                     dis[v] = dis[u] + w;
 65                     pre[v] = i;
 66                     if(!inq[v]) {
 67                         q.push(v);
 68                         inq[v] = 1;
 69                     }
 70                 }
 71             }
 72         }
 73     }
 74     if(dis[t] == inf)
 75         return 0;
 76     return 1;
 77 }
 78 
 79 void MCMF()
 80 {
 81     while(SPFA(s)) {
 82         int temp = inf;
 83         for(int i = pre[t]; i; i = pre[e[i].u]) {
 84             temp = min(temp, e[i].w);
 85         }
 86         for(int i = pre[t]; i; i = pre[e[i].u]) {
 87             e[i].w   -= temp;
 88             e[i^1].w += temp;
 89             mincost += e[i].c * temp;
 90             //printf("maxflow:%d mincost:%d\n",maxflow, mincost);
 91         }
 92         maxflow += temp;
 93     }
 94 }
 95 
 96 int a[1007][1007];
 97 int Depth_Size = 0;
 98 
 99 inline int id1(int a, int b) {
100     return (a-1) * Depth_Size + b;
101 }
102 
103 inline int id2(int a, int b) {
104     return n * Depth_Size + (a - 1) * Depth_Size + b;
105 }
106 
107 void task1() {
108     //! 3 5 9 10 12 = 39
109     //! 2 4 10 1 10 = 27
110     init();
111     s = 0, t = n * Depth_Size * 3 + 1;
112     int temp = m + 1;
113     for ( int i = 1; i <= m; ++i ) {
114         BuildGraph(s, id1(1, i), 1, 0);
115         BuildGraph(id1(1, i), id2(1, i), 1, -a[1][i]);
116         BuildGraph(id2(1, i), id1(2, i), 1, 0);
117         BuildGraph(id2(1, i), id1(2, i + 1), 1, 0);
118         //printf("u:%d v:%d cost:%d\n",id1(1, i), id2(1, i), -a[1][i]);
119     }
120     for ( int i = 2; i <= n - 1; ++i ) {
121         for ( int j = 1; j <= temp; ++j ) {
122             BuildGraph(id1(i, j), id2(i, j), 1, -a[i][j]);
123             BuildGraph(id2(i, j), id1(i + 1, j), 1, 0);
124             BuildGraph(id2(i, j), id1(i + 1, j + 1), 1, 0);
125             //printf("u:%d v:%d cost:%d\n",id1(i, j), id2(i, j), -a[i][j]);
126         }
127         ++temp;
128     }
129     for ( int i = 1; i <= temp; ++i ) {
130         BuildGraph(id1(n, i), id2(n, i), 1, -a[n][i]);
131         BuildGraph(id2(n, i), t, 1, 0);
132         //printf("u:%d v:%d cost:%d\n",id1(n, i), id2(n, i), -a[n][i]);
133     }
134     //dbg(t);
135     MCMF();
136     //dbg(maxflow);
137     cout << -mincost << endl;
138 }
139 
140 void task2() {
141     init();
142     s = 0, t = n * Depth_Size * 3 + 1;
143     int temp = m + 1;
144     for ( int i = 1; i <= m; ++i ) {
145         BuildGraph(s, id1(1, i), 1, 0);
146         BuildGraph(id1(1, i), id2(1, i), inf, -a[1][i]);
147         BuildGraph(id2(1, i), id1(2, i), 1, 0);
148         BuildGraph(id2(1, i), id1(2, i + 1), 1, 0);
149         //printf("u:%d v:%d cost:%d\n",id1(1, i), id2(1, i), -a[1][i]);
150     }
151     for ( int i = 2; i <= n - 1; ++i ) {
152         for ( int j = 1; j <= temp; ++j ) {
153             BuildGraph(id1(i, j), id2(i, j), inf, -a[i][j]);
154             BuildGraph(id2(i, j), id1(i + 1, j), 1, 0);
155             BuildGraph(id2(i, j), id1(i + 1, j + 1), 1, 0);
156             //printf("u:%d v:%d cost:%d\n",id1(i, j), id2(i, j), -a[i][j]);
157         }
158         ++temp;
159     }
160     for ( int i = 1; i <= temp; ++i ) {
161         BuildGraph(id1(n, i), id2(n, i), inf, -a[n][i]);
162         BuildGraph(id2(n, i), t, inf, 0);
163         //printf("u:%d v:%d cost:%d\n",id1(n, i), id2(n, i), -a[n][i]);
164     }
165     //dbg(t);
166     MCMF();
167     //dbg(maxflow);
168     cout << -mincost << endl;
169 }
170 
171 void task3() {
172     init();
173     s = 0, t = n * Depth_Size * 3 + 1;
174     int temp = m + 1;
175     for ( int i = 1; i <= m; ++i ) {
176         BuildGraph(s, id1(1, i), 1, 0);
177         BuildGraph(id1(1, i), id2(1, i), inf, -a[1][i]);
178         BuildGraph(id2(1, i), id1(2, i), inf, 0);
179         BuildGraph(id2(1, i), id1(2, i + 1), inf, 0);
180         //printf("u:%d v:%d cost:%d\n",id1(1, i), id2(1, i), -a[1][i]);
181     }
182     for ( int i = 2; i <= n - 1; ++i ) {
183         for ( int j = 1; j <= temp; ++j ) {
184             BuildGraph(id1(i, j), id2(i, j), inf, -a[i][j]);
185             BuildGraph(id2(i, j), id1(i + 1, j), inf, 0);
186             BuildGraph(id2(i, j), id1(i + 1, j + 1), inf, 0);
187             //printf("u:%d v:%d cost:%d\n",id1(i, j), id2(i, j), -a[i][j]);
188         }
189         ++temp;
190     }
191     for ( int i = 1; i <= temp; ++i ) {
192         BuildGraph(id1(n, i), id2(n, i), inf, -a[n][i]);
193         BuildGraph(id2(n, i), t, inf, 0);
194         //printf("u:%d v:%d cost:%d\n",id1(n, i), id2(n, i), -a[n][i]);
195     }
196     //dbg(t);
197     MCMF();
198     //dbg(maxflow);
199     cout << -mincost << endl;
200 }
201 
202 int main()  
203 {
204     //freopen("data.txt", "r", stdin);
205     read(m); read(n);
206     Depth_Size = m;
207     for ( int i = 1; i <= n; ++i ) {
208         for ( int j = 1; j <= Depth_Size; ++j ) {
209             read(a[i][j]);
210             //printf("a[%d][%d]:%d%c",i, j, a[i][j], j == Depth_Size ? '\n' : ' ');
211         }
212         ++Depth_Size;
213     }
214     task1();
215     task2();
216     task3();
217     return 0;
218 }

View Code

   #include    <bits/stdc++.h>  
   #define    dbg(   x) cout    << #x    <<    "="    << x    << endl  
   #define    eps    1   e   -   8  
   #define    pi    acos(   -   1.0)  

   using    namespace std;  
   typedef    long    long LL;  
   const    int maxn    =    1   e   5    +   7;  
   const    int inf     =    0x   3f3f3f3f;  

   int n, m, s, t;  
   int    head[maxn],   pre[maxn],   inq[maxn],   dis[maxn];  
   int cnt    =    1;  
   int mincost    =    0, maxflow    =    0;  
   struct    edge {  
          int u,to,nxt,w,c;  
   }   e[maxn    <<    1];  

   template<   class    T>   inline    void    read(   T    &   res)  
   {  
          char c;T flag   =   1;  
          while((c   =   getchar())   <   '0'   ||c   >   '9')   if(c   ==   '-')flag   =-   1;res   =c   -   '0';  
          while((c   =   getchar())   >=   '0'   &&c   <=   '9')res   =res   *   10   +c   -   '0';res   *=flag;  
   }  

   inline    void    BuildGraph(   int    u,    int    v,    int    w,    int    cost)  
   {  
          e[   ++cnt]    = (edge){u, v,    head[u], w,  cost},    head[u]    = cnt;  
          e[   ++cnt]    = (edge){v, u,    head[v],    0,    -cost},    head[v]    = cnt;   ///反向边  
   }  

   queue   <   int   > q;  

   inline    void    init() {  
          memset(head,    0,    sizeof(head));  
          memset(pre,    0,    sizeof(pre));  
          memset(inq,    0,    sizeof(inq));  
          memset(dis,    0,    sizeof(dis));  
          memset(e,    0,    sizeof(e));  
          while(   !   q.   empty()) {  
              q.   pop();  
       }  
       mincost    = maxflow    =    0;  
       cnt    =    1;  
   }  

   bool    SPFA(   int    x)  
   {  
          memset(inq,    0,    sizeof(inq));  
          for(   int i    = s; i    <= t; i   ++) {  
              dis[i]    = inf;  
       }  
          q.   push(x);  
          dis[x]    =    0;  
          inq[x]    =    1;  
          while(   !   q.   empty()) {  
              int u    =    q.   front();  
              q.   pop();  
              inq[u]    =    0;  
              for(   int i    =    head[u]; i; i    =    e[i].   nxt) {  
                  int v    =    e[i].   to, w    =    e[i].   c;  
                  if(   e[i].   w    >    0) {  
                      if(   dis[u]    + w    <    dis[v]) {  
                          dis[v]    =    dis[u]    + w;  
                          pre[v]    = i;  
                          if(   !   inq[v]) {  
                              q.   push(v);  
                              inq[v]    =    1;  
                       }  
                   }  
               }  
           }  
       }  
          if(   dis[t]    == inf)  
              return    0;  
          return    1;  
   }  

   void    MCMF()  
   {  
          while(   SPFA(s)) {  
              int temp    = inf;  
              for(   int i    =    pre[t]; i; i    =    pre[   e[i].   u]) {  
               temp    =    min(temp,    e[i].   w);  
           }  
              for(   int i    =    pre[t]; i; i    =    pre[   e[i].   u]) {  
                  e[i].   w      -= temp;  
                  e[i   ^   1].   w    += temp;  
               mincost    +=    e[i].   c    * temp;  
               //printf("maxflow:%d mincost:%d\n",maxflow, mincost);  
           }  
           maxflow    += temp;  
       }  
   }  

   int    a[   1007][   1007];  
   int Depth_Size    =    0;  

   inline    int    id1(   int    a,    int    b) {  
          return (a   -   1)    * Depth_Size    + b;  
   }  

   inline    int    id2(   int    a,    int    b) {  
          return n    * Depth_Size    + (a    -    1)    * Depth_Size    + b;  
   }  

   void    task1() {  
       //! 3 5 9 10 12 = 39  
       //! 2 4 10 1 10 = 27  
          init();  
       s    =    0, t    = n    * Depth_Size    *    3    +    1;  
          int temp    = m    +    1;  
          for (    int i    =    1; i    <= m;    ++i ) {  
              BuildGraph(s,    id1(   1, i),    1,    0);  
              BuildGraph(   id1(   1, i),    id2(   1, i),    1,    -   a[   1][i]);  
              BuildGraph(   id2(   1, i),    id1(   2, i),    1,    0);  
              BuildGraph(   id2(   1, i),    id1(   2, i    +    1),    1,    0);  
           //printf("u:%d v:%d cost:%d\n",id1(1, i), id2(1, i), -a[1][i]);  
       }  
          for (    int i    =    2; i    <= n    -    1;    ++i ) {  
              for (    int j    =    1; j    <= temp;    ++j ) {  
                  BuildGraph(   id1(i, j),    id2(i, j),    1,    -   a[i][j]);  
                  BuildGraph(   id2(i, j),    id1(i    +    1, j),    1,    0);  
                  BuildGraph(   id2(i, j),    id1(i    +    1, j    +    1),    1,    0);  
               //printf("u:%d v:%d cost:%d\n",id1(i, j), id2(i, j), -a[i][j]);  
           }  
              ++temp;  
       }  
          for (    int i    =    1; i    <= temp;    ++i ) {  
              BuildGraph(   id1(n, i),    id2(n, i),    1,    -   a[n][i]);  
              BuildGraph(   id2(n, i), t,    1,    0);  
           //printf("u:%d v:%d cost:%d\n",id1(n, i), id2(n, i), -a[n][i]);  
       }  
       //dbg(t);  
          MCMF();  
       //dbg(maxflow);  
       cout    <<    -mincost    << endl;  
   }  

   void    task2() {  
          init();  
       s    =    0, t    = n    * Depth_Size    *    3    +    1;  
          int temp    = m    +    1;  
          for (    int i    =    1; i    <= m;    ++i ) {  
              BuildGraph(s,    id1(   1, i),    1,    0);  
              BuildGraph(   id1(   1, i),    id2(   1, i), inf,    -   a[   1][i]);  
              BuildGraph(   id2(   1, i),    id1(   2, i),    1,    0);  
              BuildGraph(   id2(   1, i),    id1(   2, i    +    1),    1,    0);  
           //printf("u:%d v:%d cost:%d\n",id1(1, i), id2(1, i), -a[1][i]);  
       }  
          for (    int i    =    2; i    <= n    -    1;    ++i ) {  
              for (    int j    =    1; j    <= temp;    ++j ) {  
                  BuildGraph(   id1(i, j),    id2(i, j), inf,    -   a[i][j]);  
                  BuildGraph(   id2(i, j),    id1(i    +    1, j),    1,    0);  
                  BuildGraph(   id2(i, j),    id1(i    +    1, j    +    1),    1,    0);  
               //printf("u:%d v:%d cost:%d\n",id1(i, j), id2(i, j), -a[i][j]);  
           }  
              ++temp;  
       }  
          for (    int i    =    1; i    <= temp;    ++i ) {  
              BuildGraph(   id1(n, i),    id2(n, i), inf,    -   a[n][i]);  
              BuildGraph(   id2(n, i), t, inf,    0);  
           //printf("u:%d v:%d cost:%d\n",id1(n, i), id2(n, i), -a[n][i]);  
       }  
       //dbg(t);  
          MCMF();  
       //dbg(maxflow);  
       cout    <<    -mincost    << endl;  
   }  

   void    task3() {  
          init();  
       s    =    0, t    = n    * Depth_Size    *    3    +    1;  
          int temp    = m    +    1;  
          for (    int i    =    1; i    <= m;    ++i ) {  
              BuildGraph(s,    id1(   1, i),    1,    0);  
              BuildGraph(   id1(   1, i),    id2(   1, i), inf,    -   a[   1][i]);  
              BuildGraph(   id2(   1, i),    id1(   2, i), inf,    0);  
              BuildGraph(   id2(   1, i),    id1(   2, i    +    1), inf,    0);  
           //printf("u:%d v:%d cost:%d\n",id1(1, i), id2(1, i), -a[1][i]);  
       }  
          for (    int i    =    2; i    <= n    -    1;    ++i ) {  
              for (    int j    =    1; j    <= temp;    ++j ) {  
                  BuildGraph(   id1(i, j),    id2(i, j), inf,    -   a[i][j]);  
                  BuildGraph(   id2(i, j),    id1(i    +    1, j), inf,    0);  
                  BuildGraph(   id2(i, j),    id1(i    +    1, j    +    1), inf,    0);  
               //printf("u:%d v:%d cost:%d\n",id1(i, j), id2(i, j), -a[i][j]);  
           }  
              ++temp;  
       }  
          for (    int i    =    1; i    <= temp;    ++i ) {  
              BuildGraph(   id1(n, i),    id2(n, i), inf,    -   a[n][i]);  
              BuildGraph(   id2(n, i), t, inf,    0);  
           //printf("u:%d v:%d cost:%d\n",id1(n, i), id2(n, i), -a[n][i]);  
       }  
       //dbg(t);  
          MCMF();  
       //dbg(maxflow);  
       cout    <<    -mincost    << endl;  
   }  

   int    main()    
   {  
       //freopen("data.txt", "r", stdin);  
          read(m);    read(n);  
       Depth_Size    = m;  
          for (    int i    =    1; i    <= n;    ++i ) {  
              for (    int j    =    1; j    <= Depth_Size;    ++j ) {  
                  read(   a[i][j]);  
               //printf("a[%d][%d]:%d%c",i, j, a[i][j], j == Depth_Size ? '\n' : ' ');  
           }  
              ++Depth_Size;  
       }  
          task1();  
          task2();  
          task3();  
          return    0;  
   }  