poj

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40

//dfs
#include<iostream>
using namespace std;
char field[105][105];
int n,m;
void dfs(int x,int y)
{
	field[x][y]='.';
	for(int dx=-1;dx<=1;dx++)
		for(int dy=-1;dy<=1;dy++)
		{
			int nx=x+dx,ny=y+dy;
			if(0<=nx && nx<n && 0<=ny && ny<m && field[nx][ny]=='W')
				dfs(nx,ny);
		}
	return ;
}
int main()
{
	ios::sync_with_stdio(false);
	cin.tie(0);
	cin>>n>>m;
	for(int i=0;i<n;i++)
		for(int j=0;j<m;j++)
		{
			cin>>field[i][j];
		}
	int res=0;
	for(int i=0;i<n;i++)
		for(int j=0;j<m;j++)
		{
			if(field[i][j]=='W') 
			{
				dfs(i,j);
				res++;
			}
		}
	cout<<res<<endl;
	return 0;
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52

#include<iostream>
#include<cstring>
#define maxn 8
#define maxm 30
#define inf 0x3f3f3f3f
using namespace std;
int n,m,p,a,b;
int t[maxn];
int d[maxm][maxm];
double dp[1<<maxn][maxm];    //dp[剩下的车票集合][目标城市]=从a到达目标城市的最短时间 
int main()
{
	while(scanf("%d%d%d%d%d",&n,&m,&p,&a,&b)==5 and !(n==0 and m==0 and p==0 and a==0 and b==0))
	{
		for(int i=0;i<n;i++) scanf("%d",&t[i]);
		memset(d,-1,sizeof(d));
		int temp1,temp2,temp3;
		for(int i=0;i<p;i++)
		{
			scanf("%d%d%d",&temp1,&temp2,&temp3);
			d[temp1-1][temp2-1]=temp3;
			d[temp2-1][temp1-1]=temp3;
		}
		
		for(int i=0;i<1<<n;i++) fill(dp[i],dp[i]+m,inf);           //注意这里要用循环初始化二维数组 //inf是因为要用到min 
		dp[(1<<n)-1][a-1]=0;
		double res=inf;                                            //inf是因为要用到min 
		for(int s=(1<<n)-1;s>=0;s--)
		{
			res=min(res,dp[s][b-1]);
			for(int v=0;v<m;v++)
			{
				for(int u=0;u<m;u++)
				{
					if(d[v][u]>=0)
					{
						for(int i=0;i<n;i++)
						{
							if(s>>i&1)
							{
								dp[s&~(1<<i)][u]=min(dp[s&~(1<<i)][u],dp[s][v]+(double)d[u][v]/t[i]);
							}
						}
					}
				}
			}
		}
		if(res==inf) printf("Impossible\n");
		else printf("%.3lf\n",res);                //discuss里面说poj用lf会wa,用f就ac ，但我试了lf也可以ac
	}
	return 0;
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68

#include<iostream>
#include<vector>
#include<cstring>
using namespace std;
int V,m;
int t1,t2;   
#define maxv 10005                     
vector<int> G[maxv];           
vector<int> rG[maxv];
vector<int> vs;                  
bool used[maxv];                
int cmp[maxv];                   

void add_edge(int from,int to){
	G[from].push_back(to);
	rG[to].push_back(from);
}

void dfs(int v){
	used[v]=true;
	for(int i=0;i<G[v].size();i++){
		if(!used[G[v][i]]) dfs(G[v][i]);
	}
	vs.push_back(v);
}

void rdfs(int v,int k){
	used[v]=true;
	cmp[v]=k;
	for(int i=0;i<rG[v].size();i++){
		if(!used[rG[v][i]]) rdfs(rG[v][i],k);
	}
}

int kosaraju_scc(){
	memset(used,0,sizeof(used));
	vs.clear();
	for(int i=0;i<V;i++) if(!used[i]) dfs(i);
	memset(used,0,sizeof(used));
	int k=0;
	for(int i=vs.size()-1;i>=0;i--) if(!used[vs[i]]) rdfs(vs[i],k++);
	return k;
}
int main(){
	cin>>V>>m;
	while(m--){
		cin>>t1>>t2;
		add_edge(t1-1,t2-1);
	}
	int k=kosaraju_scc();
	int u=0,num=0;                     //备选个数 u取得正序最后一个 
	for(int i=0;i<V;i++){
		if(cmp[i]==k-1){
			u=i;
			num++;
		}
	}
	memset(used,0,sizeof(used));
	rdfs(u,0);                         //反向判断是否都可达
	for(int i=0;i<V;i++){
		if(!used[i]){
			num=0;
			break;
		}
	} 
	cout<<num<<endl;
	return 0;
}