拓扑排序(专题）
解题报告：拓扑排序的板子题，不想说了。
#include<iostream>
#include<cstring>
using namespace std;
const int N=110,M=10010;
int q[N];
bool st[N];
int n;
int h[N],e[M],ne[M],idx;
int tt=-1,hh=0;
int din[N];
void add(int a,int b)
{
e[idx]=b,ne[idx]=h[a],h[a]=idx++;
}
int cnt;
int ans[N];
int main()
{
cin>>n;
memset(h,-1,sizeof h);
for(int i=1;i<=n;i++)
{
int x;
while(cin>>x,x)
{
add(i,x);
din[x]++;
}
}
for(int i=1;i<=n;i++)
if(!din[i]) q[++tt]=i,st[i]=true;
while(hh<=tt)
{
int t=q[hh++];
ans[cnt++]=t;
for(int i=h[t];~i;i=ne[i])
{
int j=e[i];
din[j]--;
if(!din[j]&&!st[j])
{
st[j]=true;
q[++tt]=j;
}
}
}
for(int i=0;i<cnt;i++)
cout<<ans[i]<<' ';
cout<<endl;
return 0;
}
解题报告：这道题看到第一反应是差分约束，然后拓扑排序也可以做，由于所有的边都是大于0的，如果存在环一定无解（就是拓扑排序队列长度不是n就说明存在环）。在建边上，因为是最长路所以采用a>b+w，b向a连一条w的边，然后从后往前找最长路，由于每个人奖金初始值都是100，不如把每个dist都变成1，由于求最小值，要找他的上界就等价于求最长路。最后把所有答案都加起来就是总共要发的钱了。
#include<iostream>
#include<cstring>
using namespace std;
const int N=10010,M=20010;
int q[N];
bool st[N];
int w[M];
int n;
int h[N],e[M],ne[M],idx;
int tt=-1,hh=0;
int din[N];
int dist[N];
void add(int a,int b,int c)
{
w[idx]=c,e[idx]=b,ne[idx]=h[a],h[a]=idx++;
}
int cnt;
int ans[N];
int m;
int main()
{
cin>>n>>m;
memset(h,-1,sizeof h);
while(m--)
{
int a,b;
cin>>a>>b;
add(b,a,1);
din[a]++;
}
for(int i=1;i<=n;i++)
if(!din[i]) q[++tt]=i;
while(hh<=tt)
{
int t=q[hh++];
for(int i=h[t];~i;i=ne[i])
{
int j=e[i];
din[j]--;
if(!din[j])
{
q[++tt]=j;
}
}
}
if(tt!=n-1) puts("Poor Xed");
else
{
for(int i=1;i<=n;i++)
dist[i]=100;
for(int i=0;i<n;i++)
{
int j=q[i];
for(int k=h[j];~k;k=ne[k])
{
int jj=e[k];
if(dist[jj]<dist[j]+w[k])
dist[jj]=dist[j]+w[k];
}
}
int res=0;
for(int i=1;i<=n;i++)
res+=dist[i];
cout<<res<<endl;
}
return 0;
}
解题报告：这道题直接说了他是个dag图，那直接topsort，然后问题就是如何找该点能到达的点数量呢，其实就是个dp的模型，逆序遍历拓扑序，最后的终点肯定就只能到他自己，在遍历i的时候要保证他后面的值都要算出来，所以采用逆序遍历，f[i] |= f[j] ，这里为了节约空间可以用个bitset来维护个数，1代表i能到某个位，0代表不能到，从后往前遍历，f[i][i]=1，某个点肯定能到自己。
#include<iostream>
#include<cstring>
#include<bitset>
using namespace std;
const int N=30010,M=30010;
int h[N],e[M],idx,ne[M];
int q[N];
int d[N];
bitset<N>f[N];
void add(int a,int b)
{
e[idx]=b,ne[idx]=h[a],h[a]=idx++;
}
int main()
{
int n,m;
memset(h,-1,sizeof h);
scanf("%d%d",&n,&m);
while(m--)
{
int a,b;
cin>>a>>b;
add(a,b);
d[b]++;
}
int tt=-1,hh=0;
for(int i=1;i<=n;i++)
if(!d[i]) q[++tt]=i;
while(hh<=tt)
{
int t=q[hh++];
for(int i=h[t];~i;i=ne[i])
{
int j=e[i];
d[j]--;
if(!d[j])
{
q[++tt]=j;
}
}
}
for(int i=n-1;i>=0;i--)
{
int j=q[i];
f[j][j]=1;
for(int k=h[j];~k;k=ne[k])
{
int jj=e[k];
f[j]|=f[jj];
}
}
for(int i=1;i<=n;i++)
cout<<f[i].count()<<endl;
return 0;
}
解题报告：这题虽然无头绪，但是看完题解就知道了，这是个图论的问题，从start到end之间，如果没有停靠的点就是严格小于他们，可以从他们往右边的点连一条长度为1的边，但是这样空间时间顶不住啊，大概有1e9条边，这里我们需要找一个超级源点，作为中间点来节约空间，这样就能优化成1e6条边。然后拓扑排序一遍，把1~n的点变成1，这样就能免去建一个超级源点往所有点连一条1的边的操作了。不能将1到n+m变成1，虚拟源点是不能变的，举个hack例子吧，如果这个l到r的区间是完整的，那么虚拟源点值是1,1+1可以更新dist的最大值为2，这样肯定错了。
#include<iostream>
#include<cstring>
using namespace std;
const int N=2010,M=1000010;
int h[N],e[M],idx,ne[M],w[M];
int d[N];
int n,m;
int dist[N];
int q[N];
bool st[N];
void add(int a,int b,int c)
{
e[idx]=b,w[idx]=c,ne[idx]=h[a],h[a]=idx++;
d[b]++;
}
void topsort()
{
int tt=-1,hh=0;
for(int i=1;i<=n+m;i++)
{
if(!d[i])
q[++tt]=i;
}
while(hh<=tt)
{
int t=q[hh++];
for(int i=h[t];~i;i=ne[i])
{
int j=e[i];
if((--d[j])==0)
q[++tt]=j;
}
}
}
int main()
{
cin>>n>>m;
memset(h,-1,sizeof h);
for(int i=1;i<=m;i++)
{
memset(st,0,sizeof st);
int cnt;
cin>>cnt;
int start=n,end=1;
while(cnt--)
{
int x;
cin>>x;
if(x<start)
start=x;
if(x>end)
end=x;
st[x]=true;
}
for(int j=start;j<=end;j++)
if(st[j])
add(n+i,j,1);
else
add(j,n+i,0);
}
topsort();
for(int i=1;i<=n+m;i++)
dist[i]=1;
for(int i=0;i<n+m;i++)
{
int j=q[i];
for(int k=h[j];~k;k=ne[k])
{
int jj=e[k];
if(dist[jj]<dist[j]+w[k])
dist[jj]=dist[j]+w[k];
}
}
int res=0;
for(int i=1;i<=n+m;i++)
res=max(res,dist[i]);
cout<<res<<endl;
return 0;
}
