首页 > 代码库 > codeforces781D Axel and Marston in Bitland
codeforces781D Axel and Marston in Bitland
题目链接：codeforces781D
正解：$bitset$+状压$DP$
解题报告：
考虑用$f[t][0、1][i][j]$表示从$i$出发走了$2^t$步之后走到了$j$，且第一步是走的$0$或者$1$，这个状态是否存在。
转移式子的话就是$f[t][z][i][j]$$|=$$f[t-1][z][i][k]$ & $f[t-1][z$ ^ $1][k][j]$。
但是复杂度太高了，我们考虑压位，因为反正每个状态都只记录了$0$、$1$，那么我还不如把最后那一维(也就是上面的$j$)那一维变成一个二进制数，第$j$位表示取$j$的时候是否为$1$。
$N$只有$500$，开一个$500$的$bitset$就可以了。
总复杂度：$O(\frac{n^3*log(10^{18})}{60})$。
ps：因为$bitset$是$60$位一压所以复杂度$/60$，卡常神器！
//It is made by ljh2000
//有志者，事竟成，破釜沉舟，百二秦关终属楚；苦心人，天不负，卧薪尝胆，三千越甲可吞吴。
#include <iostream>
#include <cstdlib>
#include <cstring>
#include <cstdio>
#include <cmath>
#include <algorithm>
#include <ctime>
#include <vector>
#include <queue>
#include <map>
#include <set>
#include <string>
#include <complex>
#include <bitset>
using namespace std;
typedef long long LL;
typedef long double LB;
typedef complex<double> C;
const double pi = acos(-1);
const int MAXN = 520;
const LL inf = (LL)(1e18);
int n,m;
bitset<520>f[63][2][MAXN],tmp,g;
LL ans;
inline int getint(){
int w=0,q=0; char c=getchar(); while((c<‘0‘||c>‘9‘) && c!=‘-‘) c=getchar();
if(c==‘-‘) q=1,c=getchar(); while (c>=‘0‘&&c<=‘9‘) w=w*10+c-‘0‘,c=getchar(); return q?-w:w;
}
inline void work(){
n=getint(); m=getint(); int x,y,z;
for(int i=1;i<=m;i++) {
x=getint(); y=getint(); z=getint();
f[0][z][x][y]=1;
}
for(int s=1;s<=60;s++) {
for(int i=1;i<=n;i++)
for(int k=1;k<=n;k++) {
//搞清楚第一步做出的选择!
if(f[s-1][0][i][k])
f[s][0][i]|=f[s-1][1][k];
if(f[s-1][1][i][k])
f[s][1][i]|=f[s-1][0][k];
}
}
for(int i=1;i<=n;i++)
if(f[60][0][1][i]){
printf("-1");
return ;
}
g[1]=1; int tag=0;
for(int s=59;s>=0;s--) {//贪心地选
tmp=0;//清空!!!
for(int i=1;i<=n;i++)
if(g[i]) tmp|=f[s][tag][i];
if(tmp.count()) g=tmp,ans+=(1LL<<s),tag^=1;
}
if(ans>inf) printf("-1");
else printf("%I64d",ans);
}
int main()
{
work();
return 0;
}
//有志者，事竟成，破釜沉舟，百二秦关终属楚；苦心人，天不负，卧薪尝胆，三千越甲可吞吴。
codeforces781D Axel and Marston in Bitland
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。