日狗了没有自动保存
题目找不到留言，我私发
T1 城市轰炸
题目大意
给出一张有向图，可能有环，求最长链
思路
求最长链我们可以用拓扑排序。但是拓扑排序不能有环，怎么处理呢？其实环就是一个强联通分量，所以我们可以用tarjan把强联通分量求出来，并且将其合并成一个点。这样问题就解决了。
代码
#include<cstdio>
using namespace std;
const int N=1e6+1;
int tot,top,num,ans;
int first[N],next[N],en[N];
int first1[N],next1[N],en1[N];
int dfn[N],low[N],stack[N],MS[N],r[N];
int f[N],g[N],d[N],q[N],bel[N];
bool bz[N],vis[N];
inline int read()
{
int X=0,w=1; char ch=0;
while(ch<'0' || ch>'9') {if(ch=='-') w=-1;ch=getchar();}
while(ch>='0' && ch<='9') X=(X<<3)+(X<<1)+ch-'0',ch=getchar();
return X*w;
}
inline int max(int x,int y)
{
return x>y?x:y;
}
inline int min(int x,int y)
{
return x<y?x:y;
}
inline void insert(int x,int y)
{
next[++tot]=first[x];
first[x]=tot;
en[tot]=y;
}
inline void insert1(int x,int y)
{
next1[++tot]=first1[x];
first1[x]=tot;
en1[tot]=y;
d[y]++;
}
inline void tarjan(int x)
{
MS[MS[0]=1]=x;
while(MS[0])
{
if(!dfn[x=MS[MS[0]]])
{
dfn[x]=low[x]=++tot;
r[stack[++top]=x]=first[x];
bz[x]=vis[x]=true;
}
bool enter=false;
for(int i=r[x];i;i=next[i])
if(!vis[en[i]])
{
r[x]=next[i];
MS[++MS[0]]=en[i];
enter=true;
break;
}else
if(bz[en[i]]) low[x]=min(low[x],dfn[en[i]]);
if(enter) continue;
if(dfn[x]==low[x])
{
num++;
do
{
bel[stack[top]]=num;
bz[stack[top--]]=false;
}while(stack[top+1]!=x);
}
low[MS[--MS[0]]]=min(low[MS[MS[0]]],low[x]);
}
}
int main()
{
freopen("bomb.in","r",stdin);
freopen("bomb.out","w",stdout);
int n=read(),m=read();
for(int i=1;i<=m;i++)
{
int x=read(),y=read();
insert(x,y);
}
tot=0;
for(int i=1;i<=n;i++)
if(!vis[i]) tarjan(i);
tot=0;
for(int i=1;i<=n;i++)
{
g[bel[i]]++;
for(int j=first[i];j;j=next[j])
if(bel[i]^bel[en[j]]) insert1(bel[i],bel[en[j]]);
}
int l=0,r=0;
for(int i=1;i<=n;i++)
if(!d[i]) f[q[++r]=i]=g[i];
while(l<r)
{
int x=q[++l];
if(!first1[x]) ans=max(ans,f[x]);
for(int i=first1[x];i;i=next1[i])
{
f[en1[i]]=max(f[en1[i]],f[x]+g[en1[i]]);
if(!--d[en1[i]]) q[++r]=en1[i];
}
}
printf("%d\n",ans);
return 0;
}
T2 密室
题目大意
有一坨房间，房间里可能有门或者钥匙。我们初始在房间x，要走到房间y。门通向另一个房间，但需要特定的数把钥匙才能开。求x到y的最短路径。
思路
看上去没思路，于是就写个bfs，发现bfs可以过。
代码
#include<iostream>
#include<cstdio>
#include<queue>
#include<vector>
using namespace std;
struct node
{
int dot,s,step;
node(){}
node(int x,int y,int z):dot(x),s(y),step(z){}
};
struct node1
{
int to,s;
node1(){}
node1(int x,int y):to(x),s(y){}
};
int n,m,k,a[5005];
bool b[5005][2048];
queue<node> p;
vector<node1> c[5005];
void bfs()
{
p.push(node(1,a[1],0));
while (!p.empty())
{
node u=p.front();
p.pop();
if (u.dot==n)
{
cout<<u.step;
return;
}
for (int i=0;i<c[u.dot].size();i++)
{
int v=c[u.dot][i].to;
if ((u.s&c[u.dot][i].s)==c[u.dot][i].s&&b[c[u.dot][i].to][u.s|a[v]]==0)
{
b[c[u.dot][i].to][u.s|a[v]]=1;
p.push(node(v,u.s|a[v],u.step+1));
}
}
}
}
int main()
{
freopen("room.in","r",stdin);
freopen("room.out","w",stdout);
cin>>n>>m>>k;
int x,y,z,t;
for (int i=1;i<=n;i++)
{
for (int j=1;j<=k;j++)
{
cin>>x;
a[i]=a[i]*2+x;
}
}
for (int i=1;i<=m;i++)
{
cin>>y>>z;
t=0;
for (int j=1;j<=k;j++)
{
cin>>x;
t=t*2+x;
}
c[y].push_back(node1(z,t));
}
bfs();
}
T3 序列
思路
莫队算法，专门开一篇填坑