hdu 4324

思路待整理

#include<cstdio>

#include<iostream>

#include<vector>

#include<queue>

#define maxn 2005

using namespace std;

string mapp[maxn];

int n,du[maxn];

vector<int> fuck[maxn];

void init()

{

	for(int i=0;i<maxn;i++) fuck[i].clear(),du[i]=0;

}

void in()

{

	cin>>n;

	for(int i=1;i<=n;i++) cin>>mapp[i];

	for(int i=1;i<=n;i++)

	{

		for(int j=0;j<mapp[i].size();j++)

		{

		    if(mapp[i][j]=='1')

            {

               fuck[i].push_back(j+1);// 对应位置搞清楚

               du[j+1]++;

            }

		}

	}

}

void solve()

{

   queue<int> q;

   for(int i=1;i<=n;i++) if(du[i]==0) q.push(i),du[i]=-1;

   int num=0;

   while(q.size())//思想是每次取出一个入度为零的点 然后将其指向的点的入度减一

   {

  //     cout<<".."<<endl;

       int temp=q.front();

       q.pop();

       num++;

       for(int j=0;j<fuck[temp].size();j++) du[fuck[temp][j]]--;

       for(int i=1;i<=n;i++) if(du[i]==0) q.push(i),du[i]=-1;//不断的有新的点需要加入

   }

   if(num==n) cout<<"No"<<endl;

   else cout<<"Yes"<<endl;

}

int main()

{

	cin.sync_with_stdio(false);

	int t,Case=0;

	cin>>t;

	while(t--)

	{

		init();//初始化

		in();//输入

		cout<<"Case #"<<++Case<<": ";

		solve();

	}

	return 0;

}
巴特西

hdu 4324

最新文章

热门文章
