注册 登录  
 加关注
查看详情
   显示下一条  |  关闭
温馨提示!由于新浪微博认证机制调整,您的新浪微博帐号绑定已过期,请重新绑定!立即重新绑定新浪微博》  |  关闭

fudq's AC Road

何以解忧,唯有AC!

 
 
 

日志

 
 

hdu 4324  

2013-03-03 12:54:27|  分类: ACM-hdu |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |
http://acm.hdu.edu.cn/showproblem.php?pid=4324
题意:给出一个n*n的有向图,1表示有边,0表示无边,问是否存在环。
题解:简单的拓扑排序,注意下输入。
分析:
这题杯具了,一直TLE,然后就各种优化,还是TLE,最后发现问题竟然出在输入上。。。。。
本来用邻接矩阵存图,然后发现TLE,还以为是因为数据量太大,所以改用邻接表进行存储进行优化,又是TLE,然后又进行优化了,把能够省略的数组都省略了,还是TLE。。。。。
实在没办法,搜了下网上的代码,发现有人的解题报告里说TLE可能是因为输入,于是就改了,果然A了,然后把优化前的代码改了下输入,也A了,竟然被输入坑大了。。。。

两个代码都贴一下(注意输入部分!):
未优化的,406MS

/*
* test.cpp
*
* Created on: 2013-03-03
* Author: fudq
*/
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <ctime>
#include <iostream>
#include <algorithm>
#include <queue>
#include <set>
#include <map>
#include <stack>
#include <string>
#include <vector>
#include <deque>
#include <list>
#include <functional>
#include <numeric>
#include <cctype>
using namespace std;
#define N 2001
int n,g[N][N];

bool toposort()
{
int i,j,k,ru[N],vis[N];
memset(ru,0,sizeof(ru));
memset(vis,0,sizeof(vis));
for(i=0;i<n;i++)
for(j=0;j<n;j++)
if(g[i][j]==1)
ru[j]++;
for(i=0;i<n;i++)
{
for(j=0;j<n;j++)
{
if(!vis[j] && ru[j]==0)
{
vis[j]=1;
for(k=0;k<n;k++)
if(g[j][k]==1)
ru[k]--;
break;
}
}
if(j==n)
return false;
}
return true;
}

int main()
{
#ifndef ONLINE_JUDGE
freopen("testin.txt","r",stdin);
//freopen("testout.txt","w",stdout);
#endif
int T,i,j,t;
char str[N];
scanf("%d",&T);
for(t=1;t<=T;t++)
{
scanf("%d",&n);
memset(g,0,sizeof(g));
// for(i=0;i<n;i++)
// {
// getchar();
// for(j=0;j<n;j++)
// {
// scanf("%c",&str);
// if(str=='0')
// g[i][j]=0;
// else
// g[i][j]=1;
// }
// }
for(i=0;i<n;i++)
{
scanf("%s",str);
for(j=0;j<n;j++)
g[i][j]=str[j]-'0';
}
if(!toposort())
printf("Case #%d: Yes\n",t);
else
printf("Case #%d: No\n",t);
}
return 0;
}



优化后的,203MS

/*
* test.cpp
*
* Created on: 2013-03-03
* Author: fudq
*/
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <ctime>
#include <iostream>
#include <algorithm>
#include <queue>
#include <set>
#include <map>
#include <stack>
#include <string>
#include <vector>
#include <deque>
#include <list>
#include <functional>
#include <numeric>
#include <cctype>
using namespace std;
#define N 2010
int n,g[N][N];//数据量大,g改用邻接表
int ru[N];

bool toposort()
{
int j,t,k,flag;
t=0;
while(t<n)
{
flag=0;
for(j=0;j<n;j++)
{
if(ru[j]==0)
{
t++;
flag=1;
ru[j]--;
for(k=1;k<=g[j][0];k++)
ru[g[j][k]]--;
}
}
if(flag==0)
return false;
}
return true;
}

int main()
{
#ifndef ONLINE_JUDGE
freopen("testin.txt","r",stdin);
//freopen("testout.txt","w",stdout);
#endif
int T,i,j,t;
char str[N];
scanf("%d",&T);
for(t=1;t<=T;t++)
{
scanf("%d",&n);
//init
for(i=0;i<n;i++)
g[i][0]=0;//第一列记录各行的个数
memset(ru,0,sizeof(ru));
// for(i=0;i<n;i++)
// {
// getchar();
// for(j=0;j<n;j++)
// {
// scanf("%c",&str);
// if(str=='1')
// {
// g[i][++g[i][0]]=j;
// ru[j]++;
// }
// }
// }
for(i=0;i<n;i++)
{
scanf("%s",str);
for(j=0;j<n;j++)
{
if(str[j]=='1')
{
g[i][++g[i][0]]=j;
ru[j]++;
}
}
}
if(!toposort())
printf("Case #%d: Yes\n",t);
else
printf("Case #%d: No\n",t);
}
return 0;
}


  评论这张
 
阅读(99)| 评论(0)
推荐 转载

历史上的今天

在LOFTER的更多文章

评论

<#--最新日志,群博日志--> <#--推荐日志--> <#--引用记录--> <#--博主推荐--> <#--随机阅读--> <#--首页推荐--> <#--历史上的今天--> <#--被推荐日志--> <#--上一篇,下一篇--> <#-- 热度 --> <#-- 网易新闻广告 --> <#--右边模块结构--> <#--评论模块结构--> <#--引用模块结构--> <#--博主发起的投票-->
 
 
 
 
 
 
 
 
 
 
 
 
 
 

页脚

网易公司版权所有 ©1997-2018