7.29总结 - 洛谷保存站

# A
注意到总人数极小，直接枚举三个不同的人判断即可

注意有两种判断正确的可能
```cpp
#include<bits/stdc++.h>
using namespace std;

int m , f;
bool g[10][10];
int main(){
    cin >> m;
    for( int i = 1 ; i <= m ; i++ ){
        int a , b;
        cin >> a >> b;
        g[a][b] = g[b][a] = 1;
    }
    for( int i = 1 ; i <= 5 ; i++ ){
        for( int j = i + 1 ; j <= 5 ; j++ ){
            for( int k = j + 1 ; k <= 5 ; k++ ){
                if( g[i][j] == g[j][k] && g[j][k] == g[i][k] ) f = 1;
            }
        }
    }
    if(f) cout << "WIN";
    else cout << "FAIL";
    return 0;
} 
```
# B
题目要求费用最少且不能建在仓库上

那就建在仓库旁边，显然要比建在没有仓库相邻的地方更好

但是枚举$k$个仓库和周围的点需要$O(kn)$会超时

$1\le m\le10^6$，所以上述方法会枚举许多重复的边

直接对枚举$m$条边，如果一个端点是仓库而另一个不是，就可以在另一个端点上开店，统计费用的最小值即可

注意判断当$n=k$时没有地方开店直接无解
```cpp
#include<bits/stdc++.h>
using namespace std;

int  n , m , k , vis[100005] , ans = 2e9 , a[100005];
struct node{
    int x , y , z;
} l[100005];
int main(){
    cin.tie(0);
    ios::sync_with_stdio(0);
    cin >> n >> m >> k;
    for( int i = 1 ; i <= m ; i++ ){
        int u , v , lt;
        cin >> u >> v >> lt;
        l[i] = (node){u , v , lt};
    }
    for( int i = 1 ; i <= k ; i++ ){
        cin >> a[i];
        vis[a[i]] = 1;
    }
    for( int i = 1 ; i <= m ; i++ ){
        if(vis[l[i].x] == vis[l[i].y]) continue;
        ans = min( ans , l[i].z );
    }
    if( ans > 1e9 ) cout << "-1";
    else cout << ans;
    return 0;
} 
```
# C
需要把张连通图补成**一棵树**

将删边和建边操作分开讨论：

+ 删边可以让一个连通块分开，但显然这是浪费的；也可以去掉图中的环，把图变成树。具体来说如果再遍历时通过一条边回到了遍历过的节点，就可以把这条边删了保证没有环

+ 建边可以把两棵树合并,合并起来也可以是一棵树:

```
  1       4          1
 / \   + / \  =     / \
2   3   5   6      2   3
                  /
                 4
                / \
               5   6
```
只需要把几张连通图都变成树再合并就行

注意：

1、已经删除的边不能再次遍历；

2、建双向边删除时两条边都得删~~以及这题要卡常导致我T了一发~~
```cpp
#include<bits/stdc++.h>
using namespace std;

int  n , m , vis[1000005] , ans , cnt , p;
bool vis2[1000005];
struct node{
    int x , y;
};
vector<node> g[1000005];
void dfs(int x , int fa){
    vis[x] = 1;
    for( auto i:g[x] ){
        if( i.x == fa || vis2[i.y] ) continue;
        if( vis[i.x] ){
            vis2[i.y] = 1;
            ans++;
            continue;
        }
        dfs(i.x , x);
    }
}
int main(){
    cin.tie(0);
    ios::sync_with_stdio(0);
    cin >> n >> m;
    for( int i = 1 ; i <= m ; i++ ){
        int u , v;
        cin >> u >> v;
        g[u].push_back({v , i});
        g[v].push_back({u , i});
    }
    for( int i = 1 ; i <= n ; i++ ){
        if(vis[i]) continue;
        dfs(i , 0);
        cnt++;
    }
    cout << ans + cnt - 1;
    return 0;
} 
```
# D
因为城市是一棵树，所以这一大块“从首都前往i途中经过的最后一个城市的编号”其实就是**i的父节点**

先按照旧的记录方式建图，再从$r_2$开始遍历统计每个点的父节点即可
```cpp
#include<bits/stdc++.h>
using namespace std;

int  n , r1 , r2 , ans[50005];
vector<int> g[50005];
void dfs(int x , int fa){
    ans[x] = fa;
    for( auto i:g[x] ){
        if( i == fa ) continue;
        dfs(i , x);
    }
}
int main(){
    cin >> n >> r1 >> r2;
    for( int i = 1 ; i <= n ; i++ ){
        if( i == r1 ) continue;
        int a;
        cin >> a;
        g[a].push_back(i);
        g[i].push_back(a);
    }
    dfs(r2 , 0);
    for( int i = 1 ; i <= n ; i++ ){
        if( i == r2 ) continue;
        cout << ans[i] << " ";
    }
    return 0;
} 
```
# E
一开始的道路是一个环，变成单行道了其实还是组成了一个环，只是不一定强连通

由于不能增删边只能改变道路的方向，其实总共只有两种方案能使得任意两城互通：
```
a → b       a ← b
↑   ↓ 和  ↓   ↑
c ← ...    ...→ c

(跟顺时针和逆时针差不多)
```
两种方案的费用都是固定的，如果方向与道路相反，就加$c_i$

取最小值为答案

```cpp
#include<bits/stdc++.h>
using namespace std;

int n , vis[105] , ans = 1e9;
struct node{
    int y , z;
};
vector<node> g[105];
void dfs(int x , int fa , int p){
    for( auto i:g[x] ){
        if( i.y == fa ) continue;
        if( i.y == 1 ){
            ans = min( ans , p + i.z );
            continue;
        }
        dfs(i.y , x , i.z + p);
    }
}
int main(){
    cin.tie(0);
    ios::sync_with_stdio(0);
    cin >> n;
    for( int i = 1 ; i <= n ; i++ ){
        int a , b , c;
        cin >> a >> b >> c;
        g[a].push_back({b , 0});
        g[b].push_back({a , c});
    }
    dfs(1 , 0 , 0);
    cout << ans;
    return 0;
} 
```
# F
电路排线已经确定，所以每个节点的实际功率是确定的

遍历一遍统计每个非叶子节点的实际功率

插排的最大功率可以随意调换，所以只要把最大功率大的分给实际功率大的就行

如果能保证每个节点实际功率都小于分配的排插的最大功率，说明没有任何违规用电

注意：

1、根节点是插座不能参与调换；

2、不开```long long```_____

3、根节点也有$2200W$的功率限制记得判断

```cpp
#include<bits/stdc++.h>
#define int long long
using namespace std;

int n , a[100005] , f[100005] , sum[100005] , s;
int h[100005] , c[100005] , cnt;
bool p[100005];
vector<int> g[100005];
void dfs(int x , int fa){
    if( !g[x].size() ) sum[x] = a[x] , p[x] = 1 ,s += a[x];
    for( auto i:g[x] ){
        if( i == fa ) continue;
        dfs(i , x);
        sum[x] += sum[i];
    }
}
signed main(){
    cin >> n;
    for( int i = 1 ; i <= n ; i++ ) cin >> f[i] >> a[i];
    for( int i = 1 ; i <= n ; i++ ) {
        g[f[i]].push_back(i);
    } 
    dfs(0 , -1);
    if(s > 2200){
        cout << "NO\n";
        return 0;
    }
    for( int i = 1 ; i <= n ; i++ ){
        if(p[i])    continue;
        cnt++;
        h[cnt] = sum[i];
        c[cnt] = a[i];
    }
    sort(h + 1 , h + cnt + 1);
    sort(c + 1 , c + cnt + 1);
    for( int i = 1 ; i <= cnt ; i++ ){
        if( h[i] > c[i] ){
            cout << "NO\n";
            return 0;
        }
    }
    cout << "YES\n";
    return 0;
}
```
# G
这题和[D.距离一样](https://newoj.daimayuan.top/p/P3124?tid=687f8407070b6f8651340062)
差不太多

可以“整体减空白”先把总的路线数算出来得到$n(n-1)$，再减去会被蛰的路线

还是可以分类讨论$x$和$y$的位置关系：

$dis:x$和$y$的深度之差

$f(x,y):$从$x$向上方跳$y$次

$lca(x,y)：x$和$y$的最近公共祖先

$sum_i:$以$i$为根节点的子树大小

1、$lca(x,y) = x$时,例如：
```
           1
          /
         x
        / \
       2   3
            \
             y
```
会被蛰的路线有$1\rightarrow x \rightarrow3\rightarrow y$，$2\rightarrow x \rightarrow 3 \rightarrow y$和$x\rightarrow3\rightarrow y$

也就是从$\{1,x,2\}$和$\{y\}$两个集合中各选一个排列组合

方案数是$( n - sum_{f(y , dis - 1)} ) \times sum_y$

2、$lca(x,y) = y$同理，方案数是$sum_x \times ( n - sum_{fp(x,dis - 1)} )$

3、普遍的情况：
```
           1
          /
         2
        / \
       x   3
      /     \
     4       y
```
会被蛰的路线有$4\rightarrow x \rightarrow 2 \rightarrow 3 \rightarrow y$和$x\rightarrow2\rightarrow3\rightarrow y$

方案数是$sum_x * sum_y$
```cpp
#include<bits/stdc++.h>
#define int long long 
using namespace std;

int n , x , y , sum[300005] , f[300005][21] , d[300005];
vector<int> g[300005];
void dfs(int x , int fa){
    d[x] = d[fa] + 1;
    sum[x] = 1;
    f[x][0] = fa;
    for( int i = 1 ; i <= 20 ; i++ )    f[x][i] = f[f[x][i - 1]][i - 1];
    for( auto i : g[x] ){
        if( i == fa )   continue;
        dfs(i , x);
        sum[x] += sum[i];
    }
}
int lca(int x , int y){
    if( d[x] < d[y] ) swap(x , y);
    for( int i = 20 ; i >= 0 ; i-- ){
        if( d[f[x][i]] >= d[y] ) x = f[x][i];
    }
    if( x == y ) return x;
    for( int i = 20 ; i >= 0 ; i-- ){
        if( f[x][i] != f[y][i] ){
            x = f[x][i];
            y = f[y][i];
        }
    }
    return f[x][0];
}
int fp(int x , int y){
    for( int i = 20 ; i >= 0 ; i-- ){
        if( ( 1 << i ) <= y ){
            x = f[x][i];
            y -= ( 1 << i );
        }
    }
    return x;
}
signed main(){
    cin >> n >> x >> y;
    for( int i = 1 ; i < n ; i++ ){
        int a , b;
        cin >> a >> b;
        g[a].push_back(b);
        g[b].push_back(a);
    } 
    dfs(1 , 0);
    int ans = n * ( n - 1 ) , dis = abs(d[x] - d[y]) - 1;
    if( lca(x , y) == x ) ans -= ( n - sum[fp(y , dis)] ) * sum[y];
    else if( lca(x , y) == y ) ans -= sum[x] * ( n - sum[fp(x,dis)] );
    else ans -= sum[x] * sum[y];
    cout << ans;
    return 0;
}
```
# H
若某个顶点被多个骨牌半部指向，则这些半部的圆点数量必须完全相同

但这个”半部的原点数“是未知的，考虑到$n$很小，直接$O(6^n)$搜索枚举出每个顶点代表的原点数

对于每一种情况，因为每条边最多放一个骨牌，直接枚举每一条边，如果边的两个端点组合起来所代表的骨牌没有被使用过，就可以把它用上

最后统计最小值，时间复杂度$O(6^n\times m)$

```cpp
#include<bits/stdc++.h>
using namespace std;

int n , m , a[10] , ans;
struct node{
    int a , b;
} l[50];
void dfs(int x){
    if( x > n ){
        int p[7][7] = {} , cnt = 0;
        for( int i = 1 ; i <= m ; i++ ){
            int r = a[l[i].a] , q = a[l[i].b];
            if( r > q ) swap(r , q);
            if( p[r][q] )   continue;
            cnt++;
            p[r][q] = 1;
        }
        ans = max( ans , cnt );
        return;
    }
    for( int i = 1 ; i <= 6 ; i++ ){
        a[x] = i;
        dfs(x + 1);
        a[x] = 0;
    }
}
int main(){
    cin >> n >> m;
    for( int i = 1 ; i <= m ; i++ ){
        cin >> l[i].a >> l[i].b;
    }
    dfs(1);
    cout << ans;
    return 0;
}
```
# 总结
1、F题在判断实际总功率时把所有的$a_i$都加了起来WA了三发，实际上只要加叶子节点的；

2、不开```long long```_____;

3、C里$1 \le n,m \le 10^6$忘记卡常T了一发

正在渲染内容...