档案网站建设与档案信息化,村志网站建设,wordpress的登录页面模板,常熟滨江开发区人才网题意:一个n个点的联通图(n100)的无向联通图#xff0c;还有一个长度为L序列(L200)#xff0c;问最少改变序列中几个数使得序列相邻两个数是相同或者在图中相邻 题解:dp[i][j]代表第i个数变为j的最小次数,O(n*L*n) #include bits/stdc.h
#define maxn 210
#de…题意:一个n个点的联通图(n100)的无向联通图还有一个长度为L序列(L200)问最少改变序列中几个数使得序列相邻两个数是相同或者在图中相邻 题解:dp[i][j]代表第i个数变为j的最小次数,O(n*L*n) #include bits/stdc.h
#define maxn 210
#define INF 0x3f3f3f3f
typedef long long ll;
using namespace std;
int g[maxn][maxn], a[2*maxn], dp[maxn][maxn];
int main(){int n, m, t, b, ans, c, T;scanf(%d, T);while(T--){ans INF;memset(dp, INF, sizeof(dp));memset(g, 0, sizeof(g));scanf(%d%d, n, m);for(int i0;im;i){scanf(%d%d, b, c);g[b][c] g[c][b] 1;}for(int i1;in;i) g[i][i] 1;scanf(%d, t);for(int i1;it;i)scanf(%d, a[i]);for(int i1;in;i) dp[1][i] (ia[1])?0:1;for(int i2;it;i){for(int j1;jn;j){for(int k1;kn;k){if(g[j][k] 1){dp[i][j] min(dp[i][j], dp[i-1][k]((ja[i])?0:1));}}}}for(int i1;in;i)ans min(ans, dp[t][i]);printf(%d\n, ans);}return 0;
} View Code 转载于:https://www.cnblogs.com/Noevon/p/7645631.html
