【1】Reward HDU - 2647
拓扑排序，反向建边
AC代码：
#include <bits/stdc++.h>
using namespace std;
const int N=1e4+5;
int reward[N];
vector<int>pic[N];
int n,m;
struct node
{
int num,degree;
}work[N];
queue<node>que;
int solve()
{
int ans=0,cnt=0;
while(!que.empty())
que.pop();
for(int i=1;i<=n;i++)
{
if(work[i].degree==0)
{
que.push(work[i]);
reward[i]=888;
ans+=888;
}
}
while(!que.empty())
{
node now=que.front();
que.pop();
cnt++;
for(int i=0;i<pic[now.num].size();i++)
{
int tmp=pic[now.num][i];
work[tmp].degree--;
if(work[tmp].degree==0)
{
reward[tmp]=reward[now.num]+1;
ans+=reward[tmp];//每次发现有点的度为0，就计算
que.push(work[tmp]);
}
}
}
return cnt==n?ans:-1;
}
int main()
{
while(scanf("%d%d",&n,&m)!=EOF)
{
memset(work,0,sizeof(work));
for(int i=1;i<=n;i++)
{
reward[i]=0;
pic[i].clear();
work[i].num=i;
}
int a,b;
for(int i=1;i<=m;i++)
{
scanf("%d%d",&a,&b);
pic[b].push_back(a);
work[a].degree++;
}
printf("%d\n",solve());
}
return 0;
}
错误代码：
#include <bits/stdc++.h>
using namespace std;
const int N=1e4+5;
int pre[N],reward[N];//不能用pre数组，因为一个点的父亲可能有多个，但入度先为0的不一定是pre数组里面存的点
vector<int>pic[N];
int ans,n,m,cnt;
struct node
{
int num,degree;
}work[N];
queue<node>que;
void solve()
{
while(!que.empty())
que.pop();
for(int i=1;i<=n;i++)
{
if(work[i].degree==0)
que.push(work[i]);
}
while(!que.empty())
{
node now=que.front();
que.pop();
if(pre[now.num]==now.num)
{
reward[now.num]=888;
ans+=reward[now.num];
cnt++;
}
else
{
reward[now.num]=reward[pre[now.num]]+1;
ans+=reward[now.num];
cnt++;
}
for(int i=0;i<pic[now.num].size();i++)
{
int tmp=pic[now.num][i];
work[tmp].degree--;
if(work[tmp].degree==0)
que.push(work[tmp]);
}
}
}
int main()
{
while(scanf("%d%d",&n,&m)!=EOF)
{
memset(work,0,sizeof(work));
for(int i=1;i<=n;i++)
{
pre[i]=i;
reward[i]=0;
pic[i].clear();
work[i].num=i;
}
int a,b;
for(int i=1;i<=m;i++)
{
scanf("%d%d",&a,&b);
pic[b].push_back(a);
pre[a]=b;
work[a].degree++;
}
ans=0;
cnt=0;
solve();
if(cnt<n)
printf("-1\n");
else
printf("%d\n",ans);
}
return 0;
}
【2】Legal or Not HDU - 3342
拓扑排序判环：
#include <bits/stdc++.h>
using namespace std;
const int N=105;
vector<int>pic[N];
int degree[N];
queue<int>que;
bool solve(int n)
{
int cnt=0;
while(!que.empty())
que.pop();
for(int i=0;i<n;i++)
{
if(degree[i]==0)
{
que.push(i);
cnt++;
}
}
while(!que.empty())
{
int now=que.front();
que.pop();
for(int i=0;i<pic[now].size();i++)
{
int tmp=pic[now][i];
degree[tmp]--;
if(degree[tmp]==0)
{
cnt++;
que.push(tmp);
}
}
}
return cnt==n?1:0;
}
int main()
{
int n,m;
while(scanf("%d%d",&n,&m),n)
{
int x,y;
for(int i=0;i<n;i++)
{
pic[i].clear();
degree[i]=0;
}
for(int i=1;i<=m;i++)
{
scanf("%d%d",&x,&y);
pic[x].push_back(y);
degree[y]++;
}
if(solve(n))
printf("YES\n");
else
printf("NO\n");
}
return 0;
}
【3】Triangle LOVE HDU - 4324
拓扑排序判断是否有三元环
题意：给出一任意两点间有且仅有一条单向边的有向图，要求判断这个图中是否存在仅有3个结点构成的环。
我的解法是先计算能进行拓扑排序的节点cnt，如果cnt+3<=n,再用dfs判断是否存在三元环。
AC代码：
#include <bits/stdc++.h>
using namespace std;
const int N=2010;
vector<int>pic[N];
char ss[N];
bool vis[N];
int degree[N];
queue<int>que;
bool flag;
bool solve(int n)
{
int cnt=0;
while(!que.empty())
que.pop();
for(int i=1;i<=n;i++)
{
if(degree[i]==0)
{
vis[i]=1;
que.push(i);
cnt++;
}
}
while(!que.empty())
{
int now=que.front();
que.pop();
for(int i=0;i<pic[now].size();i++)
{
int tmp=pic[now][i];
degree[tmp]--;
if(degree[tmp]==0)
{
vis[tmp]=1;
cnt++;
que.push(tmp);
}
}
}
return cnt+3<=n?1:0;
}
void dfs(int p,int s,int ps)
{
//cout<<"p="<<p<<endl;
if(p==ps&&s==3)
{
flag=1;
return;
}
if(s>3)
return;
for(int i=0;i<pic[p].size();i++)
{
int t=pic[p][i];
if(!vis[t])
dfs(t,s+1,ps);
if(flag)
return;
}
}
int main()
{
int t,cas=0;
scanf("%d",&t);
while(t--)
{
int n;
scanf("%d",&n);
for(int i=1;i<=n;i++)
{
pic[i].clear();
degree[i]=0;
vis[i]=0;
}
for(int i=1;i<=n;i++)
{
scanf("%s",ss+1);
for(int j=1;j<=n;j++)
{
if(ss[j]=='1')
{
pic[i].push_back(j);
degree[j]++;
}
}
}
printf("Case #%d: ",++cas);
flag=0;
if(solve(n))
{
for(int i=1;i<=n;i++)
{
if(!vis[i])
{
dfs(i,0,i);
if(flag)
break;
vis[i]=1;
}
}
}
if(flag)
printf("Yes\n");
else
printf("No\n");
}
return 0;
}
其实可以不用这么麻烦。!_!
题目中有一句话：“scientists find that there is love between any of two people”
此题可以一遍拓扑排序判环求解 即只需要找到一个环，
就必定存在三元环
证明如下：
假设存在一个n元环，因为a->b有边，b->a必定没边，反之也成立
所以假设有环上三个相邻的点a-> b-> c,那么如果c->a间有边，
就已经形成了一个三元环，如果c->a没边，那么a->c肯定有边，
这样就形成了一个n-1元环。。。。
所以只需证明n大于3时一定有三元环即可，显然成立。
#include <bits/stdc++.h>
using namespace std;
const int N=2010;
vector<int>pic[N];
char ss[N];
bool vis[N];
int degree[N];
queue<int>que;
bool solve(int n)
{
int cnt=0;
while(!que.empty())
que.pop();
for(int i=1;i<=n;i++)
{
if(degree[i]==0)
{
vis[i]=1;
que.push(i);
cnt++;
}
}
while(!que.empty())
{
int now=que.front();
que.pop();
for(int i=0;i<pic[now].size();i++)
{
int tmp=pic[now][i];
degree[tmp]--;
if(degree[tmp]==0)
{
vis[tmp]=1;
cnt++;
que.push(tmp);
}
}
}
return cnt==n?1:0;
}
int main()
{
int t,cas=0;
scanf("%d",&t);
while(t--)
{
int n;
scanf("%d",&n);
for(int i=1;i<=n;i++)
{
pic[i].clear();
degree[i]=0;
vis[i]=0;
}
for(int i=1;i<=n;i++)
{
scanf("%s",ss+1);
for(int j=1;j<=n;j++)
{
if(ss[j]=='1')
{
pic[i].push_back(j);
degree[j]++;
}
}
}
printf("Case #%d: ",++cas);
if(!solve(n))
printf("Yes\n");
else
printf("No\n");
}
return 0;
}
【4】Following Orders POJ - 1270
这个题目，不用拓扑排序的步骤，只根据概念就可以解决。类似输出全排列。
一直超时,最后发现是输入的问题。>_<!
AC代码：
#include <cstdio>
#include <cstring>
#include <map>
#include <vector>
using namespace std;
vector<int>pre[30];
char ss[1000];
int cnt,p[30];
bool vis[30],book[30];
void dfs(int n)
{
if(n==cnt)
{
for(int i=0;i<cnt;i++)
printf("%c",p[i]+'a');
printf("\n");
return;
}
for(int i=0;i<26;i++)
{
bool f=1;
if(vis[i]||!book[i])
continue;
for(int j=0;j<pre[i].size();j++)
{
if(!vis[pre[i][j]])
f=0;
}
if(f)
{
vis[i]=1;
p[n]=i;
dfs(n+1);
vis[i]=0;
}
}
}
int main()
{
char x,y,z;
while(gets(ss))//tle
{
memset(book,0,sizeof(book));
memset(vis,0,sizeof(vis));
memset(p,0,sizeof(p));
cnt=0;
int len=strlen(ss);
for(int i=0;i<len;i++)
{
if(ss[i]!=' ')
{
cnt++;
book[ss[i]-'a']=1;
}
}
for(int i=0;i<30;i++)
pre[i].clear();
while(scanf("%c %c%c",&x,&y,&z))
{
pre[y-'a'].push_back(x-'a');
if(z=='\n')
break;
}
dfs(0);
printf("\n");
}
return 0;
}
tle代码：
#include <cstdio>
#include <cstring>
#include <map>
#include <vector>
using namespace std;
map<char,int>mp;
vector<int>pre[25];
char cc[25];
int cnt,p[30];
bool vis[25];
void dfs(int n)
{
if(n==cnt)
{
for(int i=0;i<cnt;i++)
printf("%c",cc[p[i]]);
printf("\n");
return;
}
for(int i=1;i<=cnt;i++)
{
bool f=1;
if(vis[i])
continue;
for(int j=0;j<pre[i].size();j++)
{
if(!vis[pre[i][j]])
f=0;
}
if(f)
{
vis[i]=1;
p[n]=i;
dfs(n+1);
vis[i]=0;
}
}
}
int main()
{
char x,y,z;
while(scanf("%c%c",&x,&y)!=EOF)//tle
{
cnt=0;
mp[x]=++cnt;
cc[cnt]=x;
while(scanf("%c%c",&x,&y))
{
mp[x]=++cnt;
cc[cnt]=x;
if(y=='\n')
break;
}
memset(vis,0,sizeof(vis));
for(int i=0;i<25;i++)
pre[i].clear();
while(scanf("%c %c%c",&x,&y,&z))
{
pre[mp[y]].push_back(mp[x]);
if(z=='\n')
break;
}
dfs(0);
printf("\n");
}
return 0;
}
【5】Sorting It All Out POJ - 1094
【6】Window Pains POJ - 2585
【7】Cleaning Shifts POJ - 2376
【8】逃生 HDU - 4857
【9】Ponds HDU - 5438
【10】Paint the Grid Again ZOJ - 3780
待更新。。。
京公网安备 11010502036488号