2018.7.19 题解

日狗了没有自动保存

题目找不到留言，我私发

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 序列