pat 1013

2024-02-11 16:48
文章标签 pat 1013

本文主要是介绍pat 1013,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

1013. Battle Over Cities (25)

时间限制
400 ms
内存限制
32000 kB
代码长度限制
16000 B
判题程序
Standard
作者
CHEN, Yue

It is vitally important to have all the cities connected by highways in a war. If a city is occupied by the enemy, all the highways from/toward that city are closed. We must know immediately if we need to repair any other highways to keep the rest of the cities connected. Given the map of cities which have all the remaining highways marked, you are supposed to tell the number of highways need to be repaired, quickly.

For example, if we have 3 cities and 2 highways connecting city1-city2 and city1-city3. Then if city1 is occupied by the enemy, we must have 1 highway repaired, that is the highway city2-city3.

Input

Each input file contains one test case. Each case starts with a line containing 3 numbers N (<1000), M and K, which are the total number of cities, the number of remaining highways, and the number of cities to be checked, respectively. Then M lines follow, each describes a highway by 2 integers, which are the numbers of the cities the highway connects. The cities are numbered from 1 to N. Finally there is a line containing K numbers, which represent the cities we concern.

Output

For each of the K cities, output in a line the number of highways need to be repaired if that city is lost.

Sample Input
3 2 3
1 2
1 3
1 2 3
Sample Output
1
0
0
 
//一次通过了啊
#include <stdio.h>
#include <string.h>int map[1010][1010], vis[1010];
int record[1010];int n, m, k;void dfs(int t, int a)
{vis[t] = 1;for(int i = 1; i <= n; i++){if(i != a && map[t][i] == 1 && vis[i] == 0){dfs(i, a);}}
}int main()
{int i, j, a, b, count;while(scanf("%d%d%d", &n, &m, &k) != EOF){memset(map, 0, sizeof(map));for(i = 1; i <= m; i++){scanf("%d%d", &a, &b);map[a][b] = map[b][a] = 1;}for(i = 1; i <= k; i++){scanf("%d", &a);memset(record, 0, sizeof(record));for(j = 1, b = 0; j <= n; j++){if(map[a][j] == 1){map[a][j] = map[j][a] = 0;record[b++] = j;}}memset(vis, 0, sizeof(vis));for(j = 1, count = 0; j <= n; j++){if(vis[j] == 0 && j != a){dfs(j, a);count++;}}	printf("%d\n", count-1);for(j = 0; j < b; j++) //恢复到原来的状态map[a][record[j]] = map[record[j]][a] = 1;}}return 0;
}


这篇关于pat 1013的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/700303

相关文章

PAT甲级-1044 Shopping in Mars

题目   题目大意 一串项链上有n个钻石,输入给出每个钻石的价格。用m元买一个连续的项链子串(子串长度可为1),如果不能恰好花掉m元,就要找到最小的大于m的子串,如果有重复就输出多个,按递增顺序输出子串的前端和后端索引。 原来的思路 取连续的子串使和恰等于m,没有恰等于就找最小的大于。可以将子串依次累加,使得每个位置都是起始位置到该位置的序列和,整个数组显递增顺序,就可以用右边减左边

PAT (Advanced Level) Practice——1011,1012

1011:  链接: 1011 World Cup Betting - PAT (Advanced Level) Practice (pintia.cn) 题意及解题思路: 简单来说就是给你3行数字,每一行都是按照W,T,L的顺序给出相应的赔率。我们需要找到每一行的W,T,L当中最大的一个数,累乘的结果再乘以0.65,按照例子写出表达式即可。 同时还需要记录每一次选择的是W,T还是L

PAT (Advanced Level) Practice

1001:  题目大意: 计算 a+b 的结果,并以标准格式输出——即每三个数字一组,组之间用逗号分隔(如果数字少于四位,则不需要逗号分隔)  解析: 我们知道相加右正有负,对于样例来说 Sample Input: -1000000 9 Sample Output: -999,991 如果是从左往右,算上负号的话输出应该是-99,999,1 从右往左:-,999,991离正确

hdu 1013(水题)

题意:求一个数,各个数位相加,如果结果小于10则输出,否者递归进行数位相加。   #include <cstdio>#include <cstring>#include <string>#include <iostream>using namespace std;int result(int n){int sum = 0;while (n > 0){sum += n % 1

1013. Battle Over Cities (25) DFs

1013. Battle Over Cities (25) 时间限制 400 ms 内存限制 65536 kB 代码长度限制 16000 B 判题程序 Standard 作者 CHEN, Yue It is vitally important to have all the cities connected by highways in a

poj 1013 Counterfeit Dollar

首先我们用coin[]数组来记录,具体的对应关系的话,我们将A-L分别对应数字0-11,所以对于每个char,我们减一个‘A’就行了,这样可以对应到int coin[]上去。 首先我们明确一下: 1.如果是even的话,每一个硬币都是真的 2.如果不是的话,它有可能是真的,或者是假的。因为我先遍历了一次三个string ,遇到even的话,就把对应的coin数组中的编号给置为1了,代表这个硬

1050 String Subtraction——PAT甲级

Given two strings S1​ and S2​, S=S1​−S2​ is defined to be the remaining string after taking all the characters in S2​ from S1​. Your task is simply to calculate S1​−S2​ for any given strings. However,

【九度】题目1013:开门人和关门人

题目地址:http://ac.jobdu.com/problem.php?pid=1013 题目描述: 每天第一个到机房的人要把门打开,最后一个离开的人要把门关好。现有一堆杂乱的机房签到、签离记录,请根据记录找出当天开门和关门的人。 输入:     测试输入的第一行给出记录的总天数N ( N> 0 ),下面列出了N天的记录。      每天的记录在第一行给出记录的条目数M (M

1105 链表合并——PAT乙级

给定两个单链表 L1​=a1​→a2​→⋯→an−1​→an​ 和 L2​=b1​→b2​→⋯→bm−1​→bm​。如果 n≥2m,你的任务是将比较短的那个链表逆序,然后将之并入比较长的那个链表,得到一个形如 a1​→a2​→bm​→a3​→a4​→bm−1​⋯ 的结果。例如给定两个链表分别为 6→7 和 1→2→3→4→5,你应该输出 1→2→7→3→4→6→5。 输入格式: 输入首先在第一

1110 区块反转——PAT乙级

给定一个单链表 L,我们将每 K 个结点看成一个区块(链表最后若不足 K 个结点,也看成一个区块),请编写程序将 L 中所有区块的链接反转。例如:给定 L 为 1→2→3→4→5→6→7→8,K 为 3,则输出应该为 7→8→4→5→6→1→2→3。 输入格式: 每个输入包含 1 个测试用例。每个测试用例第 1 行给出第 1 个结点的地址、结点总个数正整数 N (≤105)、以及正整数 K (