简答题 偏难
#22094

假期计划(holiday)

假期计划(holiday)


未登录也能判分,登录后才会记录
答案与解析
正确答案:<pre class="brush:cpp;toolbar:false">#include &lt;stdio.h&gt; #include &lt;algorithm&gt; #include &lt;string.h&gt; #include &lt;cctype&gt; #include &lt;iostream&gt; #include &lt;vector&gt; #include &lt;queue&gt; using namespace std; typedef long long ll; typedef unsigned long long ull; const int INF = 0x3f3f3f3f; inline int read() {     char ch = getchar();     int x = 0, f = 1;     while (!isdigit(ch)) {         if (ch == '-') f = -1;         ch = getchar();     }     while (isdigit(ch)) {         x = (x &lt;&lt; 3) + (x &lt;&lt; 1) + ch - '0';         ch = getchar();     }     return x * f; } inline void write(int x) {     if (x &lt; 0) {         putchar('-');         x = -x;     }     if (x &gt; 9) {         write(x / 10);     }     putchar(x % 10 + '0'); } const int cp = 998244353; inline int ksm(int a, int b) {     int ret = 1;     for (; b; b &gt;&gt;= 1, a = 1ll * a * a % cp) {         if (b &amp; 1) {             ret = 1ll * ret * a % cp;         }     }     return ret; } inline int inv(int x) {     return ksm(x, cp - 2); } inline int rev(int p, int q) {     return 1LL * p * inv(q) % cp; } const int N = 2505; int n, m, K, pos[N][3], f[N][N]; ull a[N], ans; vector&lt;int&gt; G[N]; queue&lt;int&gt; Q; void bfs(int S) {     f[S][S] = 1;     Q.push(S);     while (!Q.empty()) {         int x = Q.front();         Q.pop();         for (auto v : G[x]) {             if (f[S][v] &lt; 0) {                 f[S][v] = f[S][x] + 1;                 Q.push(v);             }         }     } } void check(int A, int B, int C, int D) {     if (!A || !B || !C || !D) return;     if (A == B || A == C || A == D || B == C || B == D || C == D) return;     if (f[1][A] &gt; K || f[A][B] &gt; K || f[B][C] &gt; K || f[C][D] &gt; K || f[D][1] &gt; K) return;     ans = max(ans, a[A] + a[B] + a[C] + a[D]); } signed main() {     memset(f, -1, sizeof(f));     n = read(), m = read(), K = read() + 2;     for (int i = 2; i &lt;= n; ++i) {         cin &gt;&gt; a[i];     }     for (int i = 1, x, y; i &lt;= m; ++i) {         x = read(), y = read();         G[x].push_back(y);         G[y].push_back(x);     }     bfs(1);     for (int i = 2; i &lt;= n; ++i) {         bfs(i);         for (int j = 2; j &lt;= n; ++j) {             if (f[i][j] != -1 &amp;&amp; f[1][j] != -1 &amp;&amp; f[i][j] &lt;= K &amp;&amp; f[1][j] &lt;= K &amp;&amp; i != j) {                 int x = j;                 if (a[x] &gt; a[pos[i][0]]) swap(x, pos[i][0]);                 if (a[x] &gt; a[pos[i][1]]) swap(x, pos[i][1]);                 if (a[x] &gt; a[pos[i][2]]) swap(x, pos[i][2]);             }         }     }     for (int B = 2; B &lt;= n; ++B) {         for (int C = 2; C &lt;= n; ++C) {             if (B != C &amp;&amp; f[B][C] &lt;= K &amp;&amp; f[B][C] != -1) {                 for (int i = 0; i &lt; 3; ++i) {                     for (int j = 0; j &lt; 3; ++j) {                         check(pos[B][i], B, C, pos[C][j]);                     }                 }             }         }     }     cout &lt;&lt; ans;     return 0; }</pre><p><br/></p>
这道题暂未补解析。