codeforces 505 B. Mr. Kitayuta's Colorful Graph
http://codeforces.com/contest/505/problem/B 题意；给一个图，边有颜色。给q个查询，每个查询一对点x,y。问只经过某种颜色的边使得x能到y颜色数目。 思路：存颜色的时候卡了下。。本来打算开一个二维的set用来存颜色。。。没想明白。。后来发现。。还是用vecotr就好啊。。。多开一维度vector。。或者。。vector 用 pair 都是可以的。。。因为颜色数不多。。可以暴力枚举每种颜色做一遍dfs 看只走有这条颜色的边x能否到y。。
/* ***********************************************
Author :111qqz
Created Time :2015年12月07日 星期一 09时52分33秒
File Name :code/cf/problem/505B.cpp
************************************************ */
1#include <cstdio>
2#include <cstring>
3#include <iostream>
4#include <algorithm>
5#include <vector>
6#include <queue>
7#include <set>
8#include <map>
9#include <string>
10#include <cmath>
11#include <cstdlib>
12#include <ctime>
13#define fst first
14#define sec second
15#define lson l,m,rt<<1
16#define rson m+1,r,rt<<1|1
17#define ms(a,x) memset(a,x,sizeof(a))
18#define pi pair<int ,int >
19typedef long long LL;
1using namespace std;
2const double eps = 1E-8;
3const int dx4[4]={1,0,0,-1};
4const int dy4[4]={0,-1,1,0};
5const int inf = 0x3f3f3f3f;
6const int N=105;
7int n,m,q;
8vector<pi>edge[N];
bool vis[N];
1void dfs (int x,int y,int col)
2{
3// cout<<"x:"<<x<<" col:"<<col<<endl;
4 vis[x] = true;
5 if (x==y) return;
6 for ( int i = 0 ; i < edge[x].size(); i++)
7 {
8 pi v = edge[x][i];
9// cout<<"to:"<<v.sec<<endl;
10 if (v.sec ==col &&!vis[v.fst])
11 dfs(v.fst,y,col);
12 }
13}
14int main()
15{
16 #ifndef ONLINE_JUDGE
17 freopen("code/in.txt","r",stdin);
18 #endif
19 scanf("%d %d",&n,&m);
20 for ( int i = 0 ; i < m ; i++)
21 {
22 int x,y,z;
23 cin>>x>>y>>z;
24 edge[x].push_back(make_pair(y,z));
25 edge[y].push_back(make_pair(x,z));
26 // cnt[x][y].insert(z);
27 // cnt[y][x].insert(z);
28 }
29 scanf("%d",&q);
30 for ( int i = 0 ; i < q ; i ++)
31 {
32 int u,v;
33 scanf("%d %d",&u,&v);
34 int res = 0 ;
35 for ( int j = 0 ; j <=100 ; j++) //把j++写成了i++,调了半小时2333
36 {
37 ms(vis,false);
38 dfs(u,v,j);
39 if (vis[v]) res++;
40 }
41 cout<<res<<endl;
42 }
1 #ifndef ONLINE_JUDGE
2 fclose(stdin);
3 #endif
4 return 0;
5}