https://www.acmicpc.net/problem/17219
17219번: 비밀번호 찾기
첫째 줄에 저장된 사이트 주소의 수 N(1 ≤ N ≤ 100,000)과 비밀번호를 찾으려는 사이트 주소의 수 M(1 ≤ M ≤ 100,000)이 주어진다. 두번째 줄부터 N개의 줄에 걸쳐 각 줄에 사이트 주소와 비밀번호가 공백으로 구분되어 주어진다. 사이트 주소는 알파벳 소문자, 알파벳 대문자, 대시('-'), 마침표('.')로 이루어져 있고, 중복되지 않는다. 비밀번호는 알파벳 대문자로만 이루어져 있다. 모두 길이는 최대 20자이다. N+2번째 줄부터
www.acmicpc.net
크뜨
https://www.acmicpc.net/problem/17825
17825번: 주사위 윷놀이
첫째 줄에 주사위에서 나올 수 10개가 순서대로 주어진다.
www.acmicpc.net
문제 해석을 잘못해서 고생한 문제 말이 한칸한칸 이동이 아니라 한번에 주사위 수 만큼 이동
https://www.acmicpc.net/problem/6086
6086번: 최대 유량
문제 농사꾼 존은 소들이 충분한 물을 마시길 원했다. 그래서 농장에서 우물에서 외양간을 잇는 N개의 배수관의 지도를 만들기로 했다. 존은 아주 다양한 크기의 배수관들이 완전히 우연한 방법으로 연결돼있음을 알았다. 존은 파이프를 통과하는 유량을 계산하고 싶다. 두개의 배수관이 한줄로 연결 돼 있을 때 두 관의 유량 중 최솟값으로 흐르게 된다. 예를 들어 용량이 5인 파이프가 용량이 3인 파이프와 연결되면 한개의 용량 3짜리 파이프가 된다. +---5---+
www.acmicpc.net
dfs도 못쓰는 바보다 나는......
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
|
ll dfs(int node, int flow) {
if (node == E)
return flow;
for (int there : v[node]) {
if (vis[there] == 0 && arr[node][there] > 0) {
vis[node] = 1;
ll tem = dfs(there, min(flow, arr[node][there]));
//vis[there] =0;
if (tem) {
arr[node][there] -= tem;
arr[there][node] += tem;
return tem;
}
}
}
return 0;
}
|
주석 친 부분을 하고 있어서 시간초과 나고 있었음 끝까지 갈수만 있는지 확인하면되는 거였는데 ..ㅎ
https://www.acmicpc.net/problem/2188
2188번: 축사 배정
농부 존은 소 축사를 완성하였다. 축사 환경을 쾌적하게 유지하기 위해서, 존은 축사를 N개의 칸으로 구분하고, 한 칸에는 최대 한 마리의 소만 들어가게 계획했다. 첫 주에는 소를 임의 배정해서 축사를 운영했으나, 곧 문제가 발생하게 되었다. 바로 소가 자신이 희망하는 몇 개의 축사 외에는 들어가기를 거부하는 것이다. 농부 존을 도와 최대한 많은 수의 소가 축사에 들어갈 수 있도록 하는 프로그램을 작성하시오. 축사의 번호는 1부터 M까지 매겨져 있다.
www.acmicpc.net
https://www.acmicpc.net/problem/17412
17412번: 도시 왕복하기 1
첫째 줄에 두 정수 N(3 ≤ N ≤ 400), P(1 ≤ P ≤ 10,000)이 주어진다. 다음 P개의 줄에는 각 길이 연결하는 출발 도시와 도착 도시의 번호가 주어지며, 두 번호는 다르다.
www.acmicpc.net
https://www.acmicpc.net/problem/2316
2316번: 도시 왕복하기 2
N개의 도시가 P개의 양방향 길로 연결되어 있다. 이석원은 1번 도시와 2번 도시 사이를 오가며 워해머를 한다. 성실한 이석원은 두 도시 사이를 최대한 많이 왔다 갔다 하려 하는데, 이때 한 번 방문했던 도시(1, 2번 도시 제외)를 두 번 이상 방문하지 않으려 한다. 한 번 1번 도시와 2번 도시 사이를 오갈 때, 반드시 한 개 이상의 도시를 중간에 거쳐야 한다. 입력에는 1번 도시와 2번 도시를 연결하는 길은 없다. 도시의 번호는 1번부터 N번까지이다
www.acmicpc.net
한 점을 한번만 지나가야 한다 == 크기가 1인 1->1.5 간선 만들어서 1로 들어오면 1.5로 나가게 해주면됨
https://www.acmicpc.net/problem/5651
5651번: 완전 중요한 간선
문제 어떤 플로우 그래프가 주어졌을때, 한 간선의 용량이 1줄면 최대 유량도 1이 줄어드는 경우 그 간선을 완전 중요한 간선이라고 부른다. 그래프가 주어진 경우 완전 중요한 간선의 개수를 세어보자! 입력 입력은 여러개의 테스트케이스로 이뤄진다. 첫째 줄에는 테스트케이스의 수 K (1<=K<=15)가 주어진다. 각 테스트 케이스에는 N, M (2 <= N <= 300; 2 <= M <= 5,000)가 주어지고 각각 정점의 수와 간선의 수를 뜻한다. 1번
www.acmicpc.net
예제 그려보면 이해가 됨
https://www.acmicpc.net/problem/11495
11495번: 격자 0 만들기
문제 음수가 아닌 정수들의 격자가 주어진다. 당신은 이 격자에 다음 연산을 행할 수 있다. 1. 격자에서 가로 또는 세로로 인접한 정수 2개를 고른다. 2. 각 정수가 양수일 때 1 감소시킨다. 다음 그림은 총 4개의 연속한 연산을 2*2 격자에 가해서 모든 정수를 0으로 만든 과정을 보여준다. 위 예제에서는 모든 정수를 0으로 만들기 위해 4번의 연산을 행했다. 이보다 적은 횟수의 연산으로는 모든 정수를 0으로 만들 수 없다는 것을 쉽게 알 수 있다.
www.acmicpc.net
크트
https://www.acmicpc.net/problem/15783
15783번: 세진 바이러스
입력의 첫째 줄에 시설의 수 N(1 ≤ N ≤ 100000), 파이프의 수 M(1 ≤ M ≤ 100000)이 주어진다. 이후 두 번째 줄부터 M+1번째 줄 까지 연결된 정수 시설 A(0 ≤ A ≤ N-1), B(0 ≤ B ≤ N-1) 가 주어진다. 만약 A B가 들어온다면 A에서 B로 흐르는 것을 의미한다. 동일한 파이프는 최대 한번만 들어온다.
www.acmicpc.net
scc
https://www.acmicpc.net/problem/17267
17267번: 상남자
CTP의 대표 상남자 영조는 자유롭게 이동하는 것을 좋아한다. 그렇지만 영조는 상남자이기 때문에 위아래로만 간다. 따라서 위, 아래로는 얼마든지 이동할 수 있지만 왼쪽, 오른쪽으로는 이동하지 않는다. 하지만 영조의 행동이 답답한 영조의 친구 보성이는 영조가 위, 아래로만 가는 걸 막기 위해 영조와 같이 다니며 왼쪽으로 최대 L번 오른쪽으로 최대 R번만큼 이동할 수 있게 영조를 도와준다. 영조와 보성이는 지도 밖으로는 나가지 않는다. 갈수 있는 땅, 벽의
www.acmicpc.net
상남자 문제