upc 6.2 图论你数过天上的星星吗-环 (ring) 题目描述 输入一个城市网,点表示城市,边表示路(路是有方向的)。再输入

今晚的图论场啊qaq激动
来把这几个dalao的水题写一下

问题 E: 填色问题 (color)
时间限制: 1 Sec 内存限制: 128 MB

题目描述
有形如下列图形的地图，图中每一块区域代表一个省份，现请你用红（1）、蓝（2）、黄（3）、绿（4）四种颜色给这些省份填上颜色，要求每一省份用一种颜色，且任意两个相邻省份的颜色不能相同，请给出符合条件的填色方案总数。地图用无向图的形式给出，每个省份代表图上的一个顶点，边代表两个省份是相邻的。
输入
有若干行，第一行包含一个自然数n，代表地图上省份数。接下来的n行，每行有n个用空格隔开的0或1，用来描述各省份之间的相邻关系（0表示不相邻，1表示相邻）。
输出
输出数据仅一数，表示符合条件的填色方案总数。
样例输入 Copy
5
0 1 1 0 0
1 0 0 0 1
1 0 0 1 1
0 0 1 0 1
0 1 1 1 0
样例输出 Copy
168
提示
对于所有数据，1≤n≤10

思路：
图的着色问题
点与点之间的关系以矩阵的形式给出，定义一个二维数组来记录两个点之间是否有边，用dfs来跑四种颜色即可

int n; int a[15][15]; int graph[15][15]; int color[15]; ll cnt; bool check(int c) { for(int i=1;i<=n;i++){ if(graph[c][i] && color[c] == color[i]) return false; // 出现两个相邻的点颜色相同  } return true; } void dfs(itn cur) { if(cur > n) cnt++; // 说明找到一种方案  else{ for(int i=1;i<=4;i++){    color[cur] = i; if(check(cur)) dfs(cur+1);    color[cur] = 0; } } } int main(){    cin >> n; for(int i=1;i<=n;i++){ for(itn j=1;j<=n;j++){    cin >> a[i][j]; if(a[i][j] == 1){     graph[i][j] = 1;     graph[j][i] = 1; } } } dfs(1); printf("%lldn",cnt); return 0; } 

问题 F: 环 (ring)
时间限制: 1 Sec 内存限制: 128 MB

题目描述
输入一个城市网，点表示城市，边表示路（路是有方向的）。再输入起点编号，判断从起点出发，经过不同的边，是否能够回到起点。
输入
第一行两个数n,m。表示有n个点，m条边。
2到m-1行，每行有两个数，表示每条边连接的两点的编号（方向从左到右）。
最后一行一个数，表示起点编号。
输出
如果存在回路输出 yes，否则输出 no。
样例输入 Copy
5 5
1 2
2 3
3 4
4 1
3 5
1
样例输出 Copy
yes
提示
对于所有数据，1≤n,m≤20。

思路：
判断是否存在回路
用一个vector记录从当前这个点到其他的所有点（相当于一个二维数组），跑dfs如果经过这个点就标记为1，如果最后发现起点的位置又被标记，则说明回到了起点

vector<int> G[21]; int n,m,num,flag; int u,v; itn vis[21]; // 标记这个点是否走过  void dfs(int u){ if(vis[u]){   flag = 1; return ; }  vis[u] = 1; for(int i=0;i<G[u].size();i++){ // 遍历这个点的所有边  int v = G[u][i]; dfs(v); }  vis[u] = 0; } int main(){    cin >> n >> m; for(int i=1;i<=m;i++){   cin >> u >> v;   G[u].push_back(v); // 记录从这个点开始的所有边  }  cin >> num; dfs(num); if(flag) printf("yesn"); else printf("non"); return 0; } 

问题 G: 最短路径 (path)
时间限制: 1 Sec 内存限制: 128 MB

题目描述
给出一张包含n个节点m条边的无向图，请你求出图上两点s,t间的最短路径长度（请大家自行处理重边和自环）。
输入
第一行两个数n,m，分别表示节点数和边数，以空格隔开。
之后m行，每行3个数u,v,w，表示点u和v间有一条权值为w的边。
最后一行，两个数s,t表示选择的两个点，以空格隔开。
输出
输出一个数，表示s,t间最短路径的长度。
样例输入 Copy
4 3
1 2 6
1 3 4
2 4 2
3 4
样例输出 Copy
12
提示
对于100%的数据，1≤u,v≤500,1≤m≤5×104,1≤w≤5×105

思路：
弗洛伊德最短路
把题目中的点与点的权值存到dis数组里之后，跑弗洛伊德最短路即可

const int inf = 0x3f3f3f3f; ll n,m; ll d[501][501]; ll u,v,w,x,y; void Floyd(){ for(int k=1;k<=n;k++) for(int i=1;i<=n;i++) for(int j=1;j<=n;j++)                 d[i][j] = min(d[i][j],d[i][k]+d[k][j]); } int main(){             cin >> n >> m; memset(d,inf,sizeof d); for(int i=1;i<=m;i++) {         cin >> u >> v >> w;         d[u][v] = min(d[u][v],w);         d[v][u] = min(d[v][u],w); } Floyd();     cin >> x >> y; if(x == y) printf("0"); else printf("%lldn",d[x][y]); return 0; }