题意：

给你一个ｎ个点ｍ条边的无向无环图，在尽量少的节点上放灯，使得所有边都被照亮。每盏灯将照亮以它为一个端点的所有边。

在灯的总数最小的前提下，被两盏灯同时被照亮的边数应该尽量大。

solution:

这是LRJ《训练指南》上的例题。

这题教会了我一个很有用的技巧：有两个所求的值要优化，比如让a尽量小，ｂ也尽量小

那么可以转化为让 M*a+b尽量小，其中Ｍ应该是一个比“a的最大值和b的最小值之差”还要大的数

最终的答案为ans/M, ans%M

回到这题，要求放的灯总数最小，被两盏灯同时照亮的边数尽量大。

因为每条边要么被一盏灯照亮，要么被两盏灯照亮，所以可以转换为：

求：放的灯总数量最少，被一盏灯照亮的边数尽量少。

就可以变成球 M*a+b 的最小值，ａ为放置的灯数量，ｂ为被一盏灯照的边数

f[u][1]表示u点放灯时的整个子树最小值

f[u][0]表示u点不放灯时的整个子树最小值

如果u放，那么u个子结点可以选择放，也可以不放，选择其中较小的值。如果选的是不照，就要增加一条只有一个灯照的边

如果u不放，那么其子结点就必须选择要放，而且每条边都只有一个灯照

1 /************************************************************************* 2     > File Name: a.cpp 3     > Author: QWX 4     > Mail:  5     > Created Time: 2018/10/16 11:38:09 6  ************************************************************************/ 7  8  9 //{
     {
     { #include10 #include
      
       11 #include
       
        12 #include
        
         13 #include
         
          14 #include
          
           15 #include
           
            16 #include
            17 #include
             
              18 #include
              
               19 #include
               
                20 #include
                
                 21 //#include
                 
                  22 #define vi vector
                  
                   23 #define pii pair
                   
                    24 #define mp make_pair25 #define pb push_back26 #define first fi27 #define second se28 #define pw(x) (1ll << (x))29 #define sz(x) ((int)(x).size())30 #define all(x) (x).begin(),(x).end()31 #define rep(i,l,r) for(int i=(l);i<(r);i++)32 #define per(i,r,l) for(int i=(r);i>=(l);i--)33 #define FOR(i,l,r) for(int i=(l);i<=(r);i++)34 #define cl(a,b) memset(a,b,sizeof(a))35 #define fastio ios::sync_with_stdio(false);cin.tie(0);36 #define lson l , mid , ls37 #define rson mid + 1 , r , rs38 #define INF 0x3f3f3f3f39 #define LINF 0x3f3f3f3f3f3f3f3f40 #define ll long long41 #define ull unsigned long long42 #define dd(x) cout << #x << " = " << (x) << "," 43 #define de(x) cout << #x << " = " << (x) << "\n" 44 #define endl "\n"45 using namespace std;46 //}}}47 48 49 const int N=1007;50 const int Z=2000;51 52 int n,m;53 int dp[N][2];54 vi G[N];55 bool vis[N];56 57 58 void dfs(int u)59 {60 vis[u]=1;61 dp[u][0]=0;62 dp[u][1]=Z;63 for(auto v:G[u])if(!vis[v]){64 dfs(v);65 dp[u][0]+=dp[v][1]+1;66 dp[u][1]+=min(dp[v][1],dp[v][0]+1);67 }68 }69 70 int main()71 {72 fastio;73 int T;cin>>T;74 while(T--){75 rep(i,0,n)G[i].clear();76 cin>>n>>m;77 rep(i,0,m){78 int a,b; cin>>a>>b;79 G[a].pb(b);80 G[b].pb(a);81 }82 cl(vis,0);83 int ans=0;84 rep(i,0,n)if(!vis[i]){85 dfs(i);86 ans+=min(dp[i][0],dp[i][1]);87 }88 cout<

View Code

转载于:https://www.cnblogs.com/klaycf/p/9798414.html

你可能感兴趣的文章