#P2058. National Mobilization
Title Description
X State-owned \(n\) cities, \(n\) cities are interconnected and only one road can reach each other. The capital is in \(1\) city, and now there are \(m\) tasks to be completed. Each city can choose to complete one task or not. Tasks completed need to be transferred to the capital. Transfer takes time, and so does task completion. Please calculate the minimum time to complete all tasks.
Input Format
The first line is two integers\(n, m\)
Next n-1 rows with three integers per row \(x,y,w\) indicate that there is a road from city x to y and the transmission time is \(w\)
Next is the \(n\) row \(m\) column integer, and the \(i\) row \(j\) column represents the city \(i\) how long it takes to complete the task (j\)
Output Format
An integer representing the answer, in the int range
Sample
Input Data 1
6 3 1 2 1 1 3 1 2 4 1 2 5 1 3 6 1 3 4 3 3 2 5 6 1 2 1 8 9 8 8 1 4 7 6
Output Data 1
7
Data size and conventions
50% of the data has n<=10, m<=5.
100% data n<=55, m<=11, guaranteed n>=m.
Solution
Just saw this question thought it was a normal tree \(\text{DP}\), and the result was that the equation was pushed for half a day without being pushed out, and then looked at the data range... Okay, there must be a shape pressure, and the compressed content must be related to \(m\).
Starting with the size of \(m\), state compression is relevant to \(m\), so state compression should store the completion of a task, which is obviously \(2^11\) in size and can be saved entirely. Now you can think about it in the normal tree \(\text{DP}\).
Set \(f[x][i]\) the minimum time for task completion to be \(i\) in a subtree rooted in \(x\). Considering the source of \(f[x][i]\), first i f \(x\) is a leaf node, then \(f[x][i]\) must be guaranteed u builting_popcount(i)==1 (\(i\) There is only one \(1\)) in binary because leaf nodes can only complete one task in total, so updating leaf nodes is simple, direct\(f[x][(1<(k-1))]=cost[x][k]\)(\(k\) means the \(k\) task.
Then we need to think about the transfer of non-leaf nodes. Obviously, non-leaf nodes should have two sources of state:
Don't do your own job
In this case, \(f[x][i]\) is completely transferred from the child nodes. Which states can be transferred from the child nodes? Obviously, you can only move from a subset of \(i\), but another very tricky problem arises, that is, I don't know how much each child node contributes to the states of the parent node, and if one enumeration goes directly up to \(\text O(n2^{2m})\), it's completely overwhelming for this topic. So how do I update this state?
Because we are a downward \(\text{DFS}\\\\\\\\\\\\\\\\\\\{{f[x][i]=\\\\{{{{{f[x][x][i][i], f[son_x], t \subseteq i\). It is worth noting that since the second dimension subscripts of the \(f\) array accessed when updating \(f[x][i]\) must be less than \(i\), and the \(f\) we want to avoid being accessed has been updated by the current node (otherwise, several tasks will be performed on one node), the enumeration of \(i\) should be from large to small (understandable with \(01\) backpacks).
Do a task yourself
This situation is actually getting better on the basis of the previous one. Assuming that the current node \(x\) does a task \(t\) and becomes \(i\), i t can be broken down into the current node \(x\) in state \(i\\\text {^} (1< < (t-1)\) minimum time to complete the task and the time required to complete the task \(t\). Knowing this, the transfer equation can be derived: (f[x][i]=\min\{f[x][i], f[x][i\text ^(1<(t-1)]+cost[x][t]\}\. Also note that when updating \(f[x][i]\) here, the accessed \(f\) is also located at a location smaller than \(i), so you also need to enumerate \(i\) in reverse order to avoid doing more tasks.
Initialize \(f\) as a maximum before you start, but be aware that this maximum cannot be too large, as it involves addition during the transfer process. If you don't brainstorm 0x7fffffff directly, it will overflow the addition calculation, causing the answer to become negative, and you will be happy to mention \(\text{WA}\) (of course, I can't if you use \(\text{unsigned}\). It is also important to note that when all the second dimension of \(f\) is \(0\), the initial value should be \(0\). (Since nothing happens at that time, it must be \(0\).
In addition, when the code is implemented, attention should be paid to the sequence of transfers of the above \(\text{DP}\). The transfers of self-made tasks should be placed behind the transfers of self-made tasks, because the transfers of self-made tasks need information without task transfers, which is explained above.
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<limits.h>
#include<cmath>
#define mem(a,b) memset(a,b,sizeof(a))
using namespace std;
template<typename T> void read(T &k)
{
k=0;
T flag=1;char b=getchar();
while (b<'0' || b>'9') {flag=(b=='-')?-1:1;b=getchar();}
while (b>='0' && b<='9') {k=(k<<3)+(k<<1)+(b^48);b=getchar();}
k*=flag;
}
const int _SIZE=55,_STATSIZE=(1<<11);
int n,m;
struct EDGE{
int next,to,len;
}edge[(_SIZE<<1)+5];
int tot,head[_SIZE+5],InDe[_SIZE+5];
void AddEdge(int x,int y,int v)
{
++tot;
edge[tot].next=head[x];
edge[tot].to=y;
edge[tot].len=v;
InDe[y]++;
head[x]=tot;
}
int f[_SIZE+5][_STATSIZE+5];
int cost[_SIZE+5][_SIZE+5];
void dfs(int x,int fa)
{
for (int i=head[x];i;i=edge[i].next)
{
int twd=edge[i].to,c=edge[i].len;
if (twd==fa) continue;
dfs(twd,x);
for (int i=(1<<m)-1;i;i--)
for (int t=i;t;t=(t-1)&i)
{
f[x][i]=min(f[twd][t]+f[x][i^t]+c,f[x][i]);
}
}
for (int i=(1<<m)-1;i;i--)
for (int k=0;k<m;k++)
if (i>>k&1) f[x][i]=min(f[x][i],f[x][i^(1<<k)]+cost[x][k+1]);
}
int main()
{
read(n),read(m);
for (int i=1;i<n;i++)
{
int a,b,c;
read(a),read(b),read(c);
AddEdge(a,b,c);
AddEdge(b,a,c);
}
for (int i=1;i<=n;i++)
for(int j=1;j<=m;j++)
read(cost[i][j]);
for (int i=1;i<=n;i++)
for (int j=1;j<1<<m;j++)
f[i][j]=INT_MAX>>2;//Prevent overflow
dfs(1,0);
printf("%d\n",f[1][(1<<m)-1]);
return 0;
}
Another tree shape is pressing \(\text{DP}\).