其他题目在下面---
题目链接：hdoj 1285
2647：很久以前写的了---
越想越难
这星期要ac （这里还有一个可爱的故事---嘿嘿）
额，先放两个wrong 代码，，希望给你们启发，，，
第三个ac...没用vector
第四个用STL——vector的正在努力中。。。。。。。。。。
代码1：//用的矩阵。。。Memory Limit Exceeded
#include<cstdio>
#include<queue>
#include<cstring>
#include<algorithm>
using namespace std;
int n,m,jisuan,a,b,s;
int rudu[10100];
bool map[10100][10100];
bool fafe[10100];
void topo()
{
queue<int> que;
for (int i=1;i<=n;i++)
if (rudu[i]==0)
{
jisuan++;
que.push(i);
}
while (!que.empty())
{
int now=que.front();
que.pop();
for (int i=1;i<=n;i++)
{
if (map[i][now])
{
rudu[i]--;
map[i][now]=false;
s++;
if (rudu[i]==0)
{
que.push(i);
jisuan++;
}
}
}
}
}
int main()
{
while (~scanf("%d%d",&n,&m))
{
memset(map,false,sizeof(map));
memset(rudu,0,sizeof(rudu));
for (int i=0;i<m;i++)
{
scanf("%d%d",&a,&b);
map[a][b]=true;
rudu[a]++;
}
s=888*n;
jisuan=0;
topo();
if (jisuan==n)
printf("%d\n",s);
else
printf("-1\n");
}
return 0;
}#include<cstdio>
#include<queue>
#include<cstring>
#include<algorithm>
using namespace std;
int n,m,jisuan,a,b,s;
/*struct node{
int ge;
int rushu;
int shu;
bool friend operator <(node xx,node yy)
{
return xx.rushu>yy.rushu;
}
};*/
int rudu[10100];
//bool map[10100][10100];
int aaaa[20050],bbbb[20050];
bool fafe[10100];
void topo()
{
queue<int> que;
for (int i=1;i<=n;i++)
if (rudu[i]==0)
{
jisuan++;
que.push(i);
}
while (!que.empty())
{
int now=que.front();
que.pop();
for (int i=0;i<m;i++)
{
if (bbbb[i]==now)
{
bbbb[i]=0;
int kk=aaaa[i];
rudu[kk]--;
s++;
if (rudu[kk]==0)
{
que.push(kk);
jisuan++;
}
}
}
/*for (int i=1;i<=n;i++)
{
if (map[i][now])
{
rudu[i]--;
map[i][now]=0;
// map[i][now]=false;
s++;
if (rudu[i]==0)
{
que.push(i);
jisuan++;
}
}
}*/
}
}
int main()
{
while (~scanf("%d%d",&n,&m))
{
//memset(map,0,sizeof(map));
memset(rudu,0,sizeof(rudu));
for (int i=0;i<m;i++)
{
scanf("%d%d",&a,&b);
aaaa[i]=a;
bbbb[i]=b;
//map[a][b]=1;
rudu[a]++;
}
s=888*n;
jisuan=0;
topo();
if (jisuan==n)
printf("%d\n",s);
else
printf("-1\n");
}
return 0;
}正确代码：发现上一个代码最后n加上的是m
。。。先已更正。。。。。。
#include<cstdio>
#include<queue>
#include<cstring>
#include<algorithm>
using namespace std;
int n,m,jisuan,a,b,s;
int rudu[10100];
int aaaa[20050],bbbb[20050];
bool fafe[10100];
void topo()
{
queue<int> que;
memset(fafe,true,sizeof(fafe));
int ss=0;
while (1)
{
int pp=0;
for (int i=1;i<=n;i++)
if (rudu[i]==0&&fafe[i])
{
pp=1;
jisuan++;
que.push(i);
}
if (pp==0)
break;
while (!que.empty())
{
int now=que.front();
que.pop();s+=ss;
fafe[now]=false;
for (int i=0;i<m;i++)
{
if (bbbb[i]==now)
{
bbbb[i]=0;
int kk=aaaa[i];
rudu[kk]--;
}
}
}
ss++;
}
}
int main()
{
while (~scanf("%d%d",&n,&m))
{
memset(rudu,0,sizeof(rudu));
memset(aaaa,0,sizeof(aaaa));
memset(bbbb,0,sizeof(bbbb));
for (int i=0;i<m;i++)
{
scanf("%d%d",&a,&b);
aaaa[i]=a;
bbbb[i]=b;
rudu[a]++;
}
s=888*n;
jisuan=0;
topo();
if (jisuan==n)
printf("%d\n",s);
else
printf("-1\n");
}
return 0;
}链式前向星存图31ms过
代码：
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
struct node{
int to,next;
}edge[20200];
int indegree[10100];
int head[10100],kp;
int que[10100],ll;
int n,m,s;
void topo()
{
int lp=0;
while (true)
{
ll=0;
for (int i=1;i<=n;i++)
if (indegree[i]==0)
{
indegree[i]=-1;
kp++;
s+=lp;
que[ll++]=i;
}
if (ll==0)
break;
for (int i=0;i<ll;i++)
{
for (int j=head[que[i]];j!=-1;j=edge[j].next)
{
indegree[edge[j].to]--;
}
}
lp++;
}
}
int main()
{
while (~scanf("%d%d",&n,&m))
{
memset(indegree,0,sizeof(indegree));
memset(edge,0,sizeof(edge));
for (int i=1;i<=n;i++)
head[i]=-1;int a,b;
for (int i=0;i<m;i++)
{
scanf("%d%d",&a,&b);
edge[i].to=a;
edge[i].next=head[b];
head[b]=i;
indegree[a]++;
}
kp=0;s=n*888;
topo();
if (kp==n)
printf("%d\n",s);
else
printf("-1\n");
}
return 0;
}题目链接：hdoj 2647
有重复数据--要么在加度时处理只一次-要么在减入度时一下减完
代码：
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
int n,m;
int map[600][600];
int indegree[600];
int que[600],kp;
void topo()
{
bool fafe[600];
memset(fafe,true,sizeof(fafe));
for (int ii=0;ii<n;ii++)
{
int i;
for (i=1;i<=n;i++)
if (fafe[i]&&indegree[i]==0)
break;
fafe[i]=false;
que[kp++]=i;
for (int j=1;j<=n;j++)
if (fafe[j]&&map[i][j])
{
indegree[j]-=map[i][j];
map[i][j]=0;
}
}
}
int main()
{
while (~scanf("%d%d",&n,&m))
{
memset(map,0,sizeof(map));
memset(indegree,0,sizeof(indegree));
int a,b;
for (int i=0;i<m;i++)
{
scanf("%d%d",&a,&b);
map[a][b]++;
indegree[b]++;
}
kp=1;
topo();
for (int i=1;i<kp-1;i++)
printf("%d ",que[i]);
printf("%d\n",que[kp-1]);
}
return 0;
}题目链接： hdoj 4857
思路：
当一个人排好队了，有在他前面的人可能入度也为0了--
我们就要考虑他前面那个应该排到哪里--
所以普通的for循环一次一次查答案一定不正确--
数据：
1
5 1
5 4
答案应该是1 2 3 5 4
如果我们从后面找--找到一个就跳出删点---答案是对的-但是超时--
所以我们就要用优先队列了----（开始想用dfs--发现还要考虑深度什么的--会wrong）
每次找到一个点后--删入度（并看是否有所删入度的点入度已为0---就加入队列）
就行了---
代码：
#include<cstdio>
#include<cstring>
#include<vector>
#include<queue>
#include<algorithm>
using namespace std;
struct node{
int to,next;
}edge[200200];
int indegree[30100];
int head[30100],kp;
int ll,shu;
int ans[30300],ppp;
int n,m,s;
void topo()
{
priority_queue<int >que;
for (int i=1;i<=n;i++)
{
if (indegree[i]==0)
{
que.push(i);
indegree[i]=-1;
}
}
while (!que.empty())
{
int xx=que.top();
que.pop();
ans[ppp++]=xx;
for (int i=head[xx];i!=-1;i=edge[i].next)
{
indegree[edge[i].to]--;
if (indegree[edge[i].to]==0)
{
indegree[edge[i].to]=-1;
que.push(edge[i].to);
}
}
}
}
int main()
{
int t;scanf("%d",&t);
while (t--)
{
scanf("%d%d",&n,&m);
memset(indegree,0,sizeof(indegree));
memset(edge,0,sizeof(edge));
for (int i=1;i<=n;i++)
head[i]=-1;int a,b;
for (int i=0;i<m;i++)
{
scanf("%d%d",&a,&b);
edge[i].to=a;
edge[i].next=head[b];
head[b]=i;
indegree[a]++;
}
ppp=0;
topo();
for (int i=ppp-1;i>0;i--)
printf("%d ",ans[i]);
printf("%d\n",ans[0]);
}
return 0;
}题目链接： poj 2367
代码：
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
int head[120];
struct node{
int to,next;
}dege[10000];
int in[120];
int ans[120],ll;
bool fafe[120];
int que[120],qu;
int n,a,b,kp;
void topo()
{
memset(fafe,true,sizeof(fafe));
while (true)
{
int op=0;
qu=0;
for (int i=1;i<=n;i++)
{
if (fafe[i]&&in[i]==0)
{
que[qu++]=i;
fafe[i]=false;
op=1;
ans[ll++]=i;
}
}
// printf("%d 66\n",qu);
if (!op) break;
for (int i=0;i<qu;i++)
{
for (int j=head[que[i]];j!=-1;j=dege[j].next)
{
in[dege[j].to]--;
// printf("%d %d\n",dege[j].to,in[dege[j].to]);
}
}
}
}
int main()
{
while (~scanf("%d",&n))
{
for (int i=1;i<=n;i++)
in[i]=0,head[i]=-1;kp=0;
for (int i=1;i<=n;i++)
{
while (scanf("%d",&b),b)
{
dege[kp].to=b;
dege[kp].next=head[i];
head[i]=kp++;
in[b]++;
}
}
ll=0;
topo();
for (int i=0;i<ll-1;i++)
printf("%d ",ans[i]);
printf("%d\n",ans[ll-1]);
}
return 0;
}题目链接：poj 2585
在那个4*4的方格中
1-9这每一个数都有4个固定的地方--
如果在A的4个地方有其他的数（设为B）--证明A被B覆盖--（即使图中可能不存在A--那样我们拓扑排序时一样会先排A(A 的入度为0)--然后减b的入度）
我们就建一个拓扑边A-B--意思就是A在B的里面--排序时先排A后排B
代码：
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cmath>
using namespace std;
int map[5][5];
int xx[4]={0,0,1,1};
int yy[4]={0,1,0,1};
int dis[10][10];
int in[10];
int topo()
{
int lp=0,kp=0;
while (1)
{
int i;
for (i=1;i<=9;i++)
{
if (in[i]==0)
{
kp++;in[i]=-1;break;
}
}
if (i==10)
{
if (kp==9)
return true;
return false;
}
else
{
for (int j=1;j<=9;j++)
{
if (dis[i][j])
{
in[j]-=dis[i][j];
}
}
}
}
}
int main()
{
char ch[40],pp[40]="ENDOFINPUT",dui[40]="THESE WINDOWS ARE CLEAN",cuo[40]="THESE WINDOWS ARE BROKEN";
while (scanf("%s",ch),strcmp(ch,pp))
{
for (int i=0;i<4;i++)
for (int j=0;j<4;j++)
scanf("%d",&map[i][j]);
scanf("%s",ch);
memset(in,0,sizeof(in));
memset(dis,0,sizeof(dis));
for (int i=0;i<3;i++)
{
for (int j=0;j<3;j++)
{
int a=i*3+j+1;
for (int k=0;k<4;k++)
{
int x=i+xx[k];
int y=j+yy[k];
if (map[x][y]&&map[x][y]!=a)
{
dis[a][map[x][y]]++;
in[map[x][y]]++;
}
}
}
}
if (topo())
puts(dui);
else
puts(cuo);
}
return 0;
}