洛谷___P2622 关灯问题II + P3959 宝藏 —— 状压dp

题目链接：P2622 关灯问题II╭(╯^╰)╮

题目大意：

     现有 $n$ 盏灯，以及 $m$ 个按钮。每个按钮可以同时控制这 $n$ 盏灯—— 按下了第 $i$ 个按钮，对于所有的灯都有一个效果。按下i按钮对于第 $j$ 盏灯，是下面 3 种效果之一：如果 $a[i][j]$ 为 $1$，那么当这盏灯开了的时候，把它关上，否则不管；如果为 $?1$的话，如果这盏灯是关的，那么把它打开，否则也不管；如果是 $0$，无论这灯是否开，都不管。

现在这些灯都是开的，给出所有开关对所有灯的控制效果，求问最少要按几下按钮才能全部关掉。

代码思路：

    状压dp + BFS

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair <int,int> pii;
const ll mod = 1e9 + 7;
const int maxn = 3e5 + 10;
int n, m, a[105][1005]; 
int vis[1<<15];
struct Node{int s, step;Node(){}Node(int S, int Step){s = S, step = Step;}
} q;int bfs(){queue <Node> Q;Q.push(Node((1<<n)-1, 0));vis[(1<<n)-1] = 1;while(!Q.empty()){q = Q.front();Q.pop();if(q.s==0) return q.step;for(int i=1; i<=m; i++){	//打开第 m个按钮int now = q.s;for(int j=1; j<=n; j++){if(a[i][j]==1 && (now&(1<<j-1))) now ^= (1<<j-1);else if(a[i][j]==-1 && !(now&(1<<j-1))) now |= (1<<j-1);}if(!vis[now]){vis[now] = 1;Q.push(Node(now, q.step+1));}}}return -1;	
}int main(){scanf("%d%d", &n, &m);for(int i=1; i<=m; i++)for(int j=1; j<=n; j++)scanf("%d", &a[i][j]);printf("%d", bfs()); 
}	

题目链接：P3959 宝藏╭(╯^╰)╮

题目大意：

     一张图，有 $n$ 个宝藏和 $m$ 条路，初始可任选一个宝藏点，开凿新的宝藏点，需要的代价为 $L\times K$
     $L$ 代表这条道路的长度，$K$ 代表从赞助商帮你打通的宝藏屋到这条道路起点的宝藏屋所经过的 宝藏屋的数量（包括赞助商帮你打通的宝藏屋和这条道路起点的宝藏屋）
     问找到所有宝藏的最小代价

代码思路：

    状压dp + DFS

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair <int,int> pii;
const ll mod = 1e9 + 7;
const int maxn = 3e5 + 10;
int n, m, mp[15][15];
int num[15], dp[1<<15];
int ans = INT_MAX;void dfs(int s) {for(int i=1; i<=n; i++) {	// 选择第一个点if(s & (1<<i-1)) {	// 当前状态包含这个点for(int j=1; j<=n; j++) {	//选择第二个点if(mp[i][j]!=INT_MAX && !(s&(1<<j-1))) {if(dp[s|(1<<j-1)] > dp[s] + num[i]*mp[i][j]) {num[j] = num[i] + 1;dp[s|(1<<j-1)] = dp[s] + num[i]*mp[i][j];dfs(s|(1<<j-1));}}}}}
}int main() {scanf("%d%d", &n, &m);for(int i=1; i<=n; i++)for(int j=1; j<=n; j++)mp[i][j] = INT_MAX;for(int i=1; i<=m; i++) {int x, y, z;scanf("%d%d%d", &x, &y, &z);mp[x][y] = min(mp[x][y], z);mp[y][x] = min(mp[y][x], z);}for(int i=1; i<=n; i++) {memset(dp,0x3f,sizeof(dp));memset(num,0x3f,sizeof(num));num[i] = 1;dp[1<<i-1] = 0;dfs(1<<i-1);ans = min(dp[(1<<n)-1], ans);}printf("%d\n", ans);
}