简答题 偏难
#22123

4、交通规划

4、交通规划


未登录也能判分,登录后才会记录
答案与解析
正确答案:<pre class="brush:cpp;toolbar:false">#include &lt;cstdio&gt; #include &lt;cstring&gt; #include &lt;queue&gt; #include &lt;vector&gt; #include &lt;algorithm&gt; using namespace std; typedef long long ll; const int MAXN = 360005;  // 增大数组容量适配题目规模 const ll INF = 1e18; struct Edge {     int to, rev;     ll cap;     Edge(int t, int r, ll c) : to(t), rev(r), cap(c) {} }; vector&lt;Edge&gt; g[MAXN]; int level[MAXN], iter[MAXN]; int n, m, T; // 添加双向边 void add_edge(int from, int to, ll cap) {     g[from].emplace_back(to, (int)g[to].size(), cap);     g[to].emplace_back(from, (int)g[from].size() - 1, 0);  // 反向边初始容量为0 } // BFS构建层次图 void bfs(int s) {     memset(level, -1, sizeof(level));     queue&lt;int&gt; q;     level[s] = 0;     q.push(s);     while (!q.empty()) {         int u = q.front();         q.pop();         for (const Edge&amp; e : g[u]) {             if (e.cap &gt; 0 &amp;&amp; level[e.to] &lt; 0) {                 level[e.to] = level[u] + 1;                 q.push(e.to);             }         }     } } // DFS寻找增广路 ll dfs(int u, int t, ll f) {     if (u == t) return f;     for (int&amp; i = iter[u]; i &lt; g[u].size(); ++i) {         Edge&amp; e = g[u][i];         if (e.cap &gt; 0 &amp;&amp; level[u] &lt; level[e.to]) {             ll d = dfs(e.to, t, min(f, e.cap));             if (d &gt; 0) {                 e.cap -= d;                 g[e.to][e.rev].cap += d;                 return d;             }         }     }     return 0; } // 计算最大流(最小割) ll max_flow(int s, int t) {     ll flow = 0;     while (true) {         bfs(s);         if (level[t] &lt; 0) return flow;         memset(iter, 0, sizeof(iter));         ll f;         while ((f = dfs(s, t, INF)) &gt; 0) {             flow += f;         }     } } // 射线编号转网格坐标(修正版) pair&lt;int, int&gt; get_coord(int p) {     p--;  // 转为0基索引     if (p &lt; m) {                // 上边界:(1, p+1)         return {0, p};     }     p -= m;     if (p &lt; n-1) {              // 右边界:(p+2, m)         return {p+1, m-1};     }     p -= n-1;     if (p &lt; m) {                // 下边界:(n, m-p)         return {n-1, m-1 - p};     }     p -= m;                     // 左边界:(n-p, 1)     return {n-1 - p, 0}; } int main() {     // 移除文件操作,适配标准输入输出     scanf("%d%d%d", &amp;n, &amp;m, &amp;T);          // 存储水平和垂直边的权重     vector&lt;vector&lt;ll&gt;&gt; horizontal(n-1, vector&lt;ll&gt;(m));     vector&lt;vector&lt;ll&gt;&gt; vertical(n, vector&lt;ll&gt;(m-1));          // 读取水平边(上下相邻格子)     for (int i = 0; i &lt; n-1; ++i) {         for (int j = 0; j &lt; m; ++j) {             scanf("%lld", &amp;horizontal[i][j]);         }     }          // 读取垂直边(左右相邻格子)     for (int i = 0; i &lt; n; ++i) {         for (int j = 0; j &lt; m-1; ++j) {             scanf("%lld", &amp;vertical[i][j]);         }     }          while (T--) {         int k;         scanf("%d", &amp;k);                  // 清空图结构         for (int i = 0; i &lt; MAXN; ++i) {             g[i].clear();         }                  int S = 0;                  // 源点(黑色)         int T_node = n * m + 1;     // 汇点(白色)         int node_cnt = n * m;       // 网格节点总数                  // 连接水平相邻格子(i,j)和(i+1,j)         for (int i = 0; i &lt; n-1; ++i) {             for (int j = 0; j &lt; m; ++j) {                 int u = i * m + j + 1;  // 网格节点编号从1开始                 int v = (i+1) * m + j + 1;                 ll cap = horizontal[i][j];                 add_edge(u, v, cap);                 add_edge(v, u, cap);  // 双向边             }         }                  // 连接垂直相邻格子(i,j)和(i,j+1)         for (int i = 0; i &lt; n; ++i) {             for (int j = 0; j &lt; m-1; ++j) {                 int u = i * m + j + 1;                 int v = i * m + (j+1) + 1;                 ll cap = vertical[i][j];                 add_edge(u, v, cap);                 add_edge(v, u, cap);  // 双向边             }         }                  // 处理附加点约束         for (int i = 0; i &lt; k; ++i) {             ll x3;             int p, t;             scanf("%lld%d%d", &amp;x3, &amp;p, &amp;t);                          // 获取射线对应的网格坐标             auto [r, c] = get_coord(p);             if (r &lt; 0 || r &gt;= n || c &lt; 0 || c &gt;= m) {                 // 无效坐标处理                 continue;             }                          int node = r * m + c + 1;  // 转换为节点编号                          if (t == 1) {  // 必须染黑色(连接到源点)                 add_edge(S, node, INF);    // 保证不会被割开                 add_edge(node, S, x3);     // 附加权重             } else {        // 必须染白色(连接到汇点)                 add_edge(node, T_node, INF);  // 保证不会被割开                 add_edge(T_node, node, x3);   // 附加权重             }         }                  // 计算并输出最小割(最大流)         printf("%lld\n", max_flow(S, T_node));     }          return 0; }</pre><p><br/></p>
这道题暂未补解析。