/****************************************************************
▄█ █▄ ▄████████ ▄████████ ▄█ ▀█████████▄
███ ███ ███ ███ ███ ███ ███ ███ ███
███ ███ ███ ███ ███ █▀ ███ ███ ███
▄███▄▄▄▄███▄▄ ███ ███ ███ ███ ▄███▄▄▄██▀
▀▀███▀▀▀▀███▀ ▀███████████ ▀███████████ ███ ▀▀███▀▀▀██▄
███ ███ ███ ███ ███ ███ ███ ██▄
███ ███ ███ ███ ▄█ ███ ███ ███ ███
███ █▀ ███ █▀ ▄████████▀ █▀ ▄█████████▀
****************************************************************/
#include<bits/stdc++.h>
#define FOR(i, s, e) for(int i=s; i<e; i++)
#define loop(i, n) FOR(i, 0, n)
#define sf scanf
#define pf printf
#define pb push_back
#define MP make_pair
#define fr first
#define sc second
#define ll long long
#define dd double
#define all(v) v.begin(), v.end()
#define PI acos(-1.0)
#define mem(ara, value) memset(ara, value, sizeof(ara))
#define paii pair<int, int>
#define pall pair<ll, ll>
#define SZ(a) int(a.size())
#define read(nm) freopen(nm, "r", stdin)
#define write(nm) freopen(nm, "w", stdout)
#define take(args...) asdf,args
#define dump(x) cerr<<#x<<" = "<<x<<endl
#define debug(args...) cerr,args; cerr<<endl;
using namespace std;
template<typename T>
ostream& operator<<(ostream& output, vector<T>&v)
{
output<<"[ ";
if(SZ(v))
{
output<<v[0];
}
FOR(i, 1, SZ(v))
{
output<<", "<<v[i];
}
output<<" ]";
return output;
}
template<typename T1, typename T2>
ostream& operator<<(ostream& output, pair<T1, T2>&p)
{
output<<"( "<<p.fr<<", "<<p.sc<<" )";
return output;
}
template<typename T>
ostream& operator,(ostream& output, T x)
{
output<<x<<" ";
return output;
}
struct ASDF{
ASDF& operator,(int &a) {
sf("%d", &a);
return *this;
}
ASDF& operator,(long int &a){
sf("%ld", &a);
return *this;
}
ASDF& operator,(long long int &a){
sf("%lld", &a);
return *this;
}
ASDF& operator,(char &c){
sf("%c", &c);
return *this;
}
ASDF& operator,(double &d){
sf("%lf", &d);
return *this;
}
template<typename T>
ASDF& operator,(T &a){
cin>>a;
return *this;
}
}asdf;
//Header ends here
#define MAXX 1007
vector<int>factors[MAXX];
vector<int>primes;
void generatePrimes()
{
bool isPrime[MAXX];
mem(isPrime, 1);
int root = sqrt(MAXX) + 7;
for(int i=3; i<root; i++)
{
if(isPrime[i])
{
for(int j=i*i; j<MAXX; j+=(2*i))
{
isPrime[j] = false;
}
}
}
for(int i=2; i<MAXX;)
{
if(isPrime[i])
{
for(int j=2; i*j < MAXX; j++)
{
factors[i*j].pb(i);
}
}
if(i == 2)
{
i++;
}
else
{
i += 2;
}
}
}
void init()
{
generatePrimes();
}
int bfs(int source, int target)
{
bool visited[MAXX];
int dist[MAXX];
mem(dist, -1);
mem(visited, 0);
queue<int>Q;
Q.push(source);
visited = true;
dist = 0;
while(!Q.empty())
{
int u = Q.front(); Q.pop();
loop(i, SZ(factors[u]))
{
int v = u + factors[u][i];
if( (v <= target) && !visited[v] )
{
visited[v] = true;
dist[v] = dist[u] + 1;
if(v == target)
{
break;
}
Q.push(v);
}
}
}
return dist[target];
}
int main()
{
init();
int kases, kaseno = 0;
int s, t;
sf("%d", &kases);
while(kases--)
{
sf("%d %d", &s, &t);
pf("Case %d: %d\n", ++kaseno, bfs(s, t));
}
return 0;
}
Category Archives: BFS
(USACO) Magic Squares
0
//link: http://cerberus.delos.com:790/usacoprob2?a=gfh3ra4EtuK&S=msquare
/*
ID: himuhas1
TASK: msquare
LANG: C++
*/
#include<iostream>
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<cmath>
#include<algorithm>
#include<vector>
#include<queue>
#include<stack>
#include<map>
#include<utility>
#include<set>
#define FOR(i, s, e) for(int i=s; i<e; i++)
#define loop(i, n) FOR(i, 0, n)
#define sf scanf
#define pf printf
#define pb push_back
#define MP make_pair
#define fr first
#define sc second
#define ll long long
#define dd double
#define all(v) v.begin(), v.end()
#define PI acos(-1.0)
#define mem(ara, value) memset(ara, value, sizeof(ara))
#define paii pair<int, int>
#define pall pair<ll, ll>
#define SZ(a) int(a.size())
#define read(nm) freopen(nm, "r", stdin)
#define write(nm) freopen(nm, "w", stdout)
#define dump(x) cout<<#x<<" = "<<x<<endl
using namespace std;
#define take(args...) asdf,args
#define debug(args...) asdfg,args; cout<<endl
struct ASDF{
ASDF& operator,(int &a) {
sf("%d", &a);
return *this;
}
ASDF& operator,(long int &a){
sf("%ld", &a);
return *this;
}
ASDF& operator,(long long int &a){
sf("%lld", &a);
return *this;
}
ASDF& operator,(char &c){
sf("%c", &c);
return *this;
}
ASDF& operator,(double &d){
sf("%lf", &d);
return *this;
}
template<typename T>
ASDF& operator,(T &a){
cin>>a;
return *this;
}
}asdf;
struct ASDFG{
template<typename T>
ASDFG& operator,(vector<T> &v){
pf("[");
cout<<v[0];
FOR(i, 1, SZ(v)){
cout<<", "<<v[i];
}
pf("]");
return *this;
}
template<typename T>
ASDFG& operator,(T x) {
cout<<x<<" ";
return *this;
}
}asdfg;
//Header ends here
map<string, string>nodes;
void transformA(string &s)
{
loop(i, 4)
{
swap(s[i], s[7-i]);
}
}
void transformB(string &s)
{
loop(i, 3)
{
swap(s[i], s[3]);
swap(s[7-i], s[4]);
}
}
void transformC(string &s)
{
swap(s[1], s[6]);
swap(s[5], s[6]);
swap(s[2], s[5]);
}
int main()
{
#ifndef hasibpc
read("msquare.in");
write("msquare.out");
#endif
string target;
{
char c;
loop(i, 8)
{
scanf("%c", &c);
cin.ignore();
target.push_back(c);
}
}
//dump(target);
queue<string>Q;
string current = "12345678";
nodes[current] = "-";
Q.push(current);
string ss;
string *ptr;
while(!Q.empty())
{
current = Q.front();
Q.pop();
//dump(current);
ss = current;
transformA(ss);
//dump(ss);
ptr = &nodes[ss];
if((*ptr).size() == 0)
{
*ptr = current;
if(*ptr == target) break;
Q.push(ss);
}
ss = current;
transformB(ss);
//dump(ss);
ptr = &nodes[ss];
if((*ptr).size() == 0)
{
*ptr = current;
if(*ptr == target) break;
Q.push(ss);
}
ss = current;
transformC(ss);
//dump(ss);
ptr = &nodes[ss];
if((*ptr).size() == 0)
{
*ptr = current;
if(*ptr == target) break;
Q.push(ss);
}
}
string result;
//dump(*ptr);
while(target != "12345678")
{
ptr = &nodes[target];
if((*ptr)[0] == target[7])
{
result.pb('A');
}
else if((*ptr)[0] == target[0])
{
result.pb('C');
}
else
{
result.pb('B');
}
target = *ptr;
}
reverse(all(result));
pf("%d\n", SZ(result));
cout<<result<<endl;
return 0;
}
Overfencing (USACO)
0
/*
ID: himuhas1
TASK: maze1
LANG: C++
*/
#include<iostream>
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<cmath>
#include<algorithm>
#include<vector>
#include<map>
#include<queue>
#include<stack>
#include<utility>
#include<string>
#define FOR(i, s, e) for(int i=s; i<e; i++)
#define loop(i, n) FOR(i, 0, n)
#define gi(a) sf("%d", &a)
#define gi2(a, b) sf("%d %d", &a, &b)
#define sf scanf
#define pf printf
#define pb push_back
#define fr first
#define sc second
#define MP make_pair
#define PI acos(-1.0)
#define INF 1<<29;
#define ll long long
#define paii pair<int, int>
#define all(v) v.begin(), v.end()
#define SZ(a) int(a.size())
#define dd double
#define mem(a, v) memset(a, v, sizeof(a))
#define dump(x) cout<<#x<<" = "<<(int)x<<endl;
using namespace std;
#define CONDITION -1 < tmp.fr && tmp.fr < rows && -1 < tmp.sc && tmp.sc < columns && graph[tmp.fr][tmp.sc] ==' '
int columns, rows;
char graph[202][78];
paii exits[2];
int bfs(paii u, paii v)
{
//dump(u.fr); dump(u.sc); dump(v.fr); dump(v.sc);
char dir[] = {-1, 0, 1, 0};
int dist[202][78];
bool visited[202][78];
int finalDist = 0;
mem(visited, 0);
paii tmp;
loop(i, 4)
{
tmp.fr = u.fr + dir[i];
tmp.sc = u.sc + dir[(i+1)%4];
if(CONDITION)
{
u = tmp;
break;
}
}
loop(i, 4)
{
tmp.fr = v.fr + dir[i];
tmp.sc = v.sc + dir[(i+1)%4];
if(CONDITION)
{
v = tmp;
break;
}
}
dist[u.fr][u.sc] = dist[v.fr][v.sc] = 0;
visited[u.fr][u.sc] = visited[v.fr][v.sc] = 1;
queue<paii>Q;
Q.push(u);
Q.push(v);
while(!Q.empty())
{
u = Q.front(); Q.pop();
loop(i, 4)
{
tmp.fr = u.fr + dir[i];
tmp.sc = u.sc + dir[(i+1)%4];
if(CONDITION)
{
tmp.fr += dir[i];
tmp.sc += dir[(i+1)%4];
if(CONDITION && !visited[tmp.fr][tmp.sc] )
{
//dump(u.fr); dump(u.sc); dump(tmp.fr); dump(tmp.sc); cout<<endl;
visited[tmp.fr][tmp.sc] = 1;
finalDist = max(dist[tmp.fr][tmp.sc] = dist[u.fr][u.sc] + 1, finalDist);
//dump(finalDist);
Q.push(tmp);
}
}
}
}
return finalDist+1;
}
int main()
{
#ifndef hasibpc
freopen("maze1.in", "r", stdin);
freopen("maze1.out", "w", stdout);
#endif
gi2(columns, rows);
columns = columns*2 + 1;
rows = rows*2 + 1;
cin.ignore();
loop(i, rows)
{
gets(graph[i]);
}
{
char x = 0;
for(int i=1; i<columns; i++)
{
//dump(graph[0][i]);
//dump(i);
if(graph[0][i] == ' ')
exits[x++] = MP(0, i);
if(graph[rows-1][i] == ' ')
exits[x++] = MP(rows-1, i);
}
for(int i=1; i<rows; i++)
{
//dump(graph[i][0]);
//cout<<int(graph[i][0])<<" "<<int(' ')<<endl;
if(graph[i][0] == ' ')
exits[x++] = MP(i, 0);
if(graph[i][columns-1] == ' ')
exits[x++] = MP(i, columns-1);
}
//dump(x);
}
cout<<bfs(exits[0], exits[1])<<endl;
return 0;
}
(USACO) Healthy Holsteins
0
/*
ID: himuhas1
TASK: holstein
LANG: C++
link: http://cerberus.delos.com:790/usacoprob2?S=holstein&a=9j5vF1aY3NU
*/
#include<iostream>
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<cmath>
#include<algorithm>
#include<vector>
#include<queue>
#include<stack>
#include<map>
#include<utility>
#define FOR(i, s, e) for(int i=s; i<e; i++)
#define loop(i, n) FOR(i, 0, n)
#define gi(a) sf("%d", &a)
#define gi2(a, b) sf("%d%d", &a, &b)
#define gi3(a, b, c) sf("%d%d%d", &a, &b, &c)
#define gi4(a, b, c, d) sf("%d%d%d%d", &a, &b, &c, &d)
#define sf scanf
#define pf printf
#define pb push_back
#define MP make_pair
#define fr first
#define sc second
#define ll long long
#define dd double
#define all(v) v.begin(), v.end()
#define PI acos(-1.0)
#define mem(ara, value) memset(ara, value, sizeof(ara))
#define paii pair<int, int>
#define pall pair<ll, ll>
#define SZ(a) int(a.size())
#define read freopen("input.txt", "r", stdin)
#define write freopen("output.txt", "w", stdout)
using namespace std;
#define MAXX 32772 //1<<15 + 1
#define debug
struct DATA{
int amount[26];
} scoops[MAXX], rqr, inp[16];
int countBit(int n)
{
if(n==0)
{
return 0;
}
return 1 + countBit(n>>1);
}
int main()
{
#ifndef hasibpc
freopen("holstein.in", "r", stdin);
freopen("holstein.out", "w", stdout);
#endif // hasibpc
int number_of_vitamins, G;
gi(number_of_vitamins);
loop(i, number_of_vitamins)
{
gi(rqr.amount[i]);
}
gi(G);
loop(i, G)
{
loop(j, number_of_vitamins)
{
gi(inp[i].amount[j]);
}
}
int till = (1<<(G));
mem(scoops[0].amount, 0);
/*
loop(i, G)
{
cout<<scoops[0].amount[i]<<" ";
}
*/
int pre, best = ~(1<<29);
bool valid;
FOR(i, 1, till)
{
pre = i & ~(1<<(countBit(i)-1));
//pf("i=%d, pre=%d\n", i, pre);
valid = 1;
loop(j, number_of_vitamins)
{
scoops[i].amount[j] = scoops[pre].amount[j] + inp[countBit(i)-1].amount[j];
if(scoops[i].amount[j] < rqr.amount[j])
valid = 0;
}
if(valid)
{
if(__builtin_popcount(best) > __builtin_popcount(i))
{
best = i;
//cout<<"best updated"<<endl;
}
}
#if 0
else
{
cout<<i<<" is not valid"<<endl;
loop(k, number_of_vitamins)
{
cout<<scoops[i].amount[k]<< " ";
}
cout<<endl;
}
#endif
}
//cout<<"came here"<<endl;
pf("%d", __builtin_popcount(best));
//return 00;
//cout<< "best = " << best <<endl;
for(int i=0; (1<<i) <= best; i++)
{
if(best & (1<<i))
{
pf(" %d", i+1);
}
}
puts("");
return 0;
}
(USACO) The Castle
1
/*
user: himuhas1
link: http://cerberus.delos.com:790/usacoprob2?a=0Hi6SPQOgMg&S=castle
*/
/*
ID: himuhas1
TASK: castle
LANG: C++
*/
#include<iostream>
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<cmath>
#include<algorithm>
#include<vector>
#include<queue>
#include<stack>
#include<map>
#include<utility>
#define FOR(i, s, e) for(int i=s; i<e; i++)
#define loop(i, n) FOR(i, 0, n)
#define gi(a) sf("%d", &a)
#define gi2(a, b) sf("%d%d", &a, &b)
#define gi3(a, b, c) sf("%d%d%d", &a, &b, &c)
#define gi4(a, b, c, d) sf("%d%d%d%d", &a, &b, &c, &d)
#define sf scanf
#define pf printf
#define pb push_back
#define MP make_pair
#define fr first
#define sc second
#define ll long long
#define dd double
#define all(v) v.begin(), v.end()
#define PI acos(-1.0)
#define mem(ara, value) memset(ara, value, sizeof(ara))
#define paii pair<int, int>
#define pall pair<ll, ll>
#define SZ(a) int(a.size())
#define read freopen("input.txt", "r", stdin)
#define write freopen("output.txt", "w", stdout)
#define INF 1<<29
using namespace std;
#define MAXX 52
int graph[MAXX][MAXX];
int component[MAXX][MAXX];
int column, row;
vector<int>cntElements;
bool visited[MAXX][MAXX];
char dirx[] = {-1, 0, 1, 0};
char diry[] = {0 , -1, 0, 1};
void bfs(int i, int j)
{
paii u, v;
u.fr = i;
u.sc = j;
visited[i][j] = 1;
queue<paii>Q;
Q.push(u);
while(!Q.empty())
{
u = Q.front(); Q.pop();
component[u.fr][u.sc] = SZ(cntElements) - 1;
cntElements[ component[u.fr][u.sc] ]++;
loop(i, 4)
{
if( ((graph[u.fr][u.sc] & (1<<i)) == 0 ))
{
//pf("%d & %d = %d\n", graph[u.fr][u.sc], (1<<i), 0);
v.fr = u.fr + diry[i];
v.sc = u.sc + dirx[i];
if(!visited[v.fr][v.sc])
{
//pf("(%d, %d) -> (%d, %d)\n", u.fr, u.sc, v.fr, v.sc);
visited[v.fr][v.sc] = 1;
Q.push(v);
}
}
}
//break;
}
}
void setComponent()
{
mem(visited, 0);
loop(i, row)
{
loop(j, column)
{
if(!visited[i][j])
{
cntElements.pb(0);
bfs(i, j);
}
}
}
}
int main()
{
freopen("castle.in", "r", stdin);
freopen("castle.out", "w", stdout);
int longestRoom;
gi2(column, row);
loop(i, row)
{
loop(j, column)
{
gi(graph[i][j]);
}
}
setComponent();
pf("%d\n", SZ(cntElements));
longestRoom = -INF;
loop(i, SZ(cntElements))
{
longestRoom = max(longestRoom, cntElements[i]);
}
pf("%d\n", longestRoom);
longestRoom = -1;
paii pos, v;
char ch;
for(int j=column-1; -1 < j; j--)
{
for(int i=0; i<row; i++)
{
for(int c=2; 0 < c; c--)
{
if( (graph[i][j] & (1<<c)) != 0 )
{
v.fr = i + diry[c];
v.sc = j + dirx[c];
if(v.fr < 0 || v.sc >= column) continue;
if(component[i][j] != component[ v.fr ][ v.sc ] && longestRoom <= cntElements[ component[i][j] ] + cntElements[component[ v.fr ][ v.sc ]] )
{
longestRoom = cntElements[ component[i][j] ] + cntElements[component[ v.fr ][ v.sc ]];
pos.fr = i;
pos.sc = j;
ch = (c==1?'N':'E');
}
}
}
}
}
cout<<longestRoom<<endl;
cout<<pos.fr+1<<" "<<pos.sc+1<<" "<<ch<<endl;
return 0;
}
(UVa) 571 – Jugs
0
/*
user: php
link: http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=24&page=show_problem&problem=512
*/
#include<iostream>
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<cmath>
#include<algorithm>
#include<vector>
#include<string>
#include<stack>
#include<queue>
#include<map>
#include<sstream>
#include<utility>
#define FOR(i, s, e) for(int i=s; i<e; i++)
#define loop(i, n) for(int i=0; i<n; i++)
#define getint(n) scanf("%d", &n)
#define pb(a) push_back(a)
#define ll long long
#define dd double
#define SZ(a) int(a.size())
#define read() freopen("input.txt", "r", stdin)
#define write() freopen("output.txt", "w", stdout)
#define mem(a, v) memset(a, v, sizeof(a))
#define all(v) v.begin(), v.end()
#define pi acos(-1.0)
#define INF 1<<29
#define mod abs
#define pf printf
#define sf scanf
#define mp make_pair
#define paii pair<int, int>
#define padd pair<dd, dd>
#define pall pair<ll, ll>
#define fr first
#define sc second
using namespace std;
#define MAXX 1002
pair<int, paii>state[MAXX][MAXX];
bool visited[MAXX][MAXX];
int target;
int cA, cB;
vector<int>result;
string command[] = {"fill A", "fill B", "empty A", "empty B", "pour A B", "pour B A"};
void bfs()
{
mem(visited, 0);
paii u, v;
u.fr = u.sc = 0;
visited[0][0] = 1;
queue<paii>Q;
Q.push(u);
int quan;
while(!Q.empty())
{
u = Q.front(); Q.pop();
//change 1
v = u;
v.fr = cA;
if(!visited[v.fr][v.sc])
{
state[v.fr][v.sc].fr = 0;
state[v.fr][v.sc].sc = u;
visited[v.fr][v.sc] = 1;
if(v.sc == target) break;
Q.push(v);
}
//change 2
v = u;
v.sc = cB;
if(!visited[v.fr][v.sc])
{
state[v.fr][v.sc].fr = 1;
state[v.fr][v.sc].sc = u;
visited[v.fr][v.sc] = 1;
if(v.sc == target) break;
Q.push(v);
}
//change 3
v = u;
v.fr = 0;
if(!visited[v.fr][v.sc])
{
state[v.fr][v.sc].fr = 2;
state[v.fr][v.sc].sc = u;
visited[v.fr][v.sc] = 1;
if(v.sc == target) break;
Q.push(v);
}
//change 4
v = u;
v.sc = 0;
if(!visited[v.fr][v.sc])
{
state[v.fr][v.sc].fr = 3;
state[v.fr][v.sc].sc = u;
visited[v.fr][v.sc] = 1;
if(v.sc == target) break;
Q.push(v);
}
//change 5
v = u;
quan = min(v.fr, cB - v.sc);
v.fr -= quan;
v.sc += quan;
if(!visited[v.fr][v.sc])
{
state[v.fr][v.sc].fr = 4;
state[v.fr][v.sc].sc = u;
visited[v.fr][v.sc] = 1;
if(v.sc == target) break;
Q.push(v);
}
//change 6
v = u;
quan = min(v.sc, cA - v.fr);
v.sc -= quan;
v.fr += quan;
if(!visited[v.fr][v.sc])
{
state[v.fr][v.sc].fr = 5;
state[v.fr][v.sc].sc = u;
visited[v.fr][v.sc] = 1;
if(v.sc == target) break;
Q.push(v);
}
}
result.clear();
while(v.fr + v.sc != 0)
{
result.pb( state[v.fr][v.sc].fr );
v = state[v.fr][v.sc].sc;
}
reverse(all(result));
loop(i, SZ(result))
{
cout<<command[ result[i] ]<<endl;
}
cout<<"success"<<endl;
}
int main()
{
while(sf("%d %d %d", &cA, &cB, &target) == 3)
{
bfs();
}
return 0;
}
(USACO) Mother’s Milk
0
/*
ID: himuhas1
TASK: milk3
LANG: C++
*/
#include<iostream>
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<cmath>
#include<algorithm>
#include<vector>
#include<string>
#include<stack>
#include<queue>
#include<map>
#include<sstream>
#include<utility>
#define FOR(i, s, e) for(int i=s; i<e; i++)
#define loop(i, n) for(int i=0; i<n; i++)
#define getint(n) scanf("%d", &n)
#define pb(a) push_back(a)
#define ll long long
#define dd double
#define SZ(a) int(a.size())
#define read() freopen("input.txt", "r", stdin)
#define write() freopen("output.txt", "w", stdout)
#define mem(a, v) memset(a, v, sizeof(a))
#define all(v) v.begin(), v.end()
#define pi acos(-1.0)
#define INF 1<<29
#define mod abs
#define pf printf
#define sf scanf
#define mp make_pair
#define paii pair<int, int>
#define padd pair<dd, dd>
#define pall pair<ll, ll>
#define fr first
#define sc second
using namespace std;
#define MAXX 21
struct DATA{
int q[3];
}u,v;
int maxAbility[3];
bool visited[MAXX][MAXX][MAXX];
vector<int>result;
void bfs()
{
visited[u.q[0]][u.q[1]][u.q[2]] = 1;
queue<DATA>Q;
Q.push(u);
int quantity;
while(!Q.empty())
{
u = Q.front(); Q.pop();
if(u.q[0] == 0) result.pb(u.q[2]);
loop(i, 3)
{
loop(j, 3)
{
if(i == j) continue;
loop(k, 3) v.q[k] = u.q[k];
quantity = min(u.q[i], maxAbility[j] - u.q[j]);
v.q[i] -= quantity;
v.q[j] += quantity;
if(!visited[v.q[0]][v.q[1]][v.q[2]])
{
visited[v.q[0]][v.q[1]][v.q[2]] = 1;
Q.push(v);
}
}
}
}
}
int main()
{
freopen("milk3.in", "r", stdin);
freopen("milk3.out", "w", stdout);
loop(i, 3) cin>>maxAbility[i];
u.q[0] = u.q[1] = 0;
u.q[2] = maxAbility[2];
bfs();
sort(all(result));
pf("%d", result[0]);
FOR(i, 1, SZ(result))
pf(" %d", result[i]);
pf("\n");
return 0;
}
(USACO) The Clocks (IOI’94-DAY 2)
0
/*
user: himuhas1
link: http://cerberus.delos.com:790/usacoprob2?a=dTQL99FvdOh&S=clocks
*/
/*
ID: himuhas1
TASK: clocks
LANG: C++
*/
#include<iostream>
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<cmath>
#include<algorithm>
#include<vector>
#include<string>
#include<stack>
#include<queue>
#include<map>
#include<sstream>
#include<utility>
#define FOR(i, s, e) for(int i=s; i<e; i++)
#define loop(i, n) for(int i=0; i<n; i++)
#define getint(n) scanf("%d", &n)
#define pb(a) push_back(a)
#define ll long long
#define dd double
#define SZ(a) int(a.size())
#define read() freopen("input.txt", "r", stdin)
#define write() freopen("output.txt", "w", stdout)
#define mem(a, v) memset(a, v, sizeof(a))
#define all(v) v.begin(), v.end()
#define pi acos(-1.0)
#define INF 1<<29
#define mod abs
#define pf printf
#define sf scanf
#define mp make_pair
#define paii pair<int, int>
#define padd pair<dd, dd>
#define pall pair<ll, ll>
#define fr first
#define sc second
using namespace std;
#define MAXX 9
#define isSet(ara, gd) ara[gd[0]][gd[1]][gd[2]][gd[3]][gd[4]][gd[5]][gd[6]][gd[7]][gd[8]]
struct DATA{
int state[9];
};
int grid[9];
string moves[MAXX];
int dir[4][4][4][4][4][4][4][4][4];
void bfs()
{
bool visited[4][4][4][4][4][4][4][4][4];
mem(visited, 0);
bool isSolution;
isSet(visited, grid) = 1;
DATA u, v;
loop(i, 9)
{
u.state[i] = grid[i];
}
queue<DATA>Q;
Q.push(u);
while(!Q.empty())
{
u = Q.front(); Q.pop();
loop(i, 9)
{
loop(j, 9)
{
v.state[j] = u.state[j];
}
loop(j, SZ(moves[i]))
{
v.state[ moves[i][j] - 'A' ] = (v.state[ moves[i][j] - 'A' ] + 1) % 4;
}
if( isSet(visited, v.state) == 0 )
{
isSet(visited, v.state) = 1;
isSolution = 1;
loop(i, 9)
{
if(v.state[i] != 3)
{
isSolution = 0;
break;
}
}
isSet(dir, v.state) = i;
if(isSolution)
{
return;
}
Q.push(v);
}
}
}
}
int main()
{
freopen("clocks.in", "r", stdin);
freopen("clocks.out", "w", stdout);
moves[0] = "ABDE";
moves[1] = "ABC";
moves[2] = "BCEF";
moves[3] = "ADG";
moves[4] = "BDEFH";
moves[5] = "CFI";
moves[6] = "DEGH";
moves[7] = "GHI";
moves[8] = "EFHI";
loop(i, 9)
{
cin>>grid[i];
grid[i] = (grid[i]/3) - 1;
}
bfs();
DATA u;
loop(i, 9) u.state[i] = 3;
vector<int>result;
int id;
bool isSolution = 1;
while(1)
{
isSolution = 1;
id = isSet(dir, u.state);
result.pb(id+1);
loop(i, SZ(moves[id]))
{
u.state[ moves[id][i] - 'A' ] = (u.state[ moves[id][i] - 'A' ] + 3) % 4;
}
loop(i, 9)
{
if(u.state[i] != grid[i])
{
isSolution = 0;
break;
}
}
if(isSolution) break;
}
sort(all(result));
cout<<result[0];
FOR(i, 1, SZ(result))
{
cout<<" "<<result[i];
}
cout<<endl;
return 0;
}
(UVa) 315 – Network
0
/*
user: php
link: http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=24&page=show_problem&problem=251
*/
#include<iostream>
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<cmath>
#include<algorithm>
#include<vector>
#include<string>
#include<stack>
#include<queue>
#include<map>
#include<sstream>
#include<utility>
#define FOR(i, s, e) for(int i=s; i<e; i++)
#define loop(i, n) for(int i=0; i<n; i++)
#define getint(n) scanf("%d", &n)
#define pb(a) push_back(a)
#define ll long long
#define dd double
#define SZ(a) int(a.size())
#define read() freopen("input.txt", "r", stdin)
#define write() freopen("output.txt", "w", stdout)
#define mem(a, v) memset(a, v, sizeof(a))
#define all(v) v.begin(), v.end()
#define pi acos(-1.0)
#define INF 1<<29
#define mod abs
#define pf printf
#define sf scanf
#define mp make_pair
#define paii pair<int, int>
#define padd pair<dd, dd>
#define pall pair<ll, ll>
#define fr first
#define sc second
using namespace std;
#define MAXX 101
int cntPlaces;
vector<int>graph[MAXX];
bool bfs(int not_to_visit)
{
bool visited[MAXX];
mem(visited, 0);
int totalVisited = 1;
int u = (not_to_visit + 1) % cntPlaces;
int v;
queue<int>Q;
Q.push(u);
visited[u] = 1;
while( !Q.empty() )
{
u = Q.front(); Q.pop();
loop(i, SZ(graph[u]))
{
v = graph[u][i];
if(v != not_to_visit)
{
if(!visited[v])
{
visited[v] = 1;
totalVisited++;
Q.push(v);
}
}
}
}
return totalVisited != (cntPlaces - 1);
}
int main()
{
string str;
stringstream ss;
int p, q;
int result;
while(1)
{
getint(cntPlaces);
if(cntPlaces == 0) break;
cin.ignore();
loop(i, cntPlaces) graph[i].clear();
while(1)
{
getline(cin, str);
if(str == "0") break;
ss.clear();
ss<<str;
ss>>p;
p--;
while(ss.good())
{
ss>>q;
q--;
graph[p].pb(q);
graph[q].pb(p);
}
}
if(cntPlaces == 1)
{
pf("0\n");
continue;
}
result = 0;
loop(i, cntPlaces)
{
if(bfs(i))
{
result++;
}
}
pf("%d\n", result);
}
return 0;
}
(UVa) 10600 – ACM Contest and Blackout
0
/*
user: php
link: http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=24&page=show_problem&problem=1541
*/
#include<iostream>
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<cmath>
#include<algorithm>
#include<vector>
#include<string>
#include<stack>
#include<queue>
#include<map>
#include<sstream>
#include<utility>
#define FOR(i, s, e) for(int i=s; i<e; i++)
#define loop(i, n) for(int i=0; i<n; i++)
#define getint(n) scanf("%d", &n)
#define pb(a) push_back(a)
#define ll long long
#define dd double
#define SZ(a) int(a.size())
#define read() freopen("input.txt", "r", stdin)
#define write() freopen("output.txt", "w", stdout)
#define mem(a, v) memset(a, v, sizeof(a))
#define all(v) v.begin(), v.end()
#define pi acos(-1.0)
#define INF 1<<29
#define mod abs
#define pf printf
#define sf scanf
#define mp make_pair
#define paii pair<int, int>
#define padd pair<dd, dd>
#define pall pair<ll, ll>
#define fr first
#define sc second
#define FEM edges[i].sc.fr
#define SEM edges[i].sc.sc
using namespace std;
#define MAXX 102
int N, M;
vector<pair<int, paii> > edges;
vector<int>graph[MAXX];
int best, secondBest;
bool secondBestDone;
int parent[MAXX];
int cost[MAXX][MAXX];
int dir[MAXX];
int find(int u)
{
if(parent[u] == u) return u;
return parent[u] = find(parent[u]);
}
void bfs(int source, int target)
{
bool visited[MAXX];
mem(visited, false);
visited = 1;
queue<int>Q;
Q.push(source);
while(!Q.empty())
{
int u = Q.front(); Q.pop();
loop(i, SZ(graph[u]))
{
int v = graph[u][i];
if(!visited[v])
{
visited[v] = 1;
dir[v] = u;
if(target == v)
{
return;
}
Q.push(v);
}
}
}
}
int cleanAndAdd(int source, int destination)
{
int maxValue = -INF;
while(source != destination)
{
//cout<<"visiting " << cost[dir]<<" cost"<<endl;
maxValue = max(maxValue, cost[dir] );
source = dir;
}
//cout<<"maxValue " <<maxValue<<endl;
return maxValue;
}
void MST()
{
best = 0;
secondBestDone = false;
secondBest = INF;
int p, q;
loop(i, SZ(edges))
{
p = find(FEM);
q = find(SEM);
if(p != q)
{
graph[ FEM ].pb(SEM);
graph[ SEM ].pb(FEM);
cost[SEM][FEM] = cost[FEM][SEM] = edges[i].fr;
parent[p] = q;
best += edges[i].fr;
}
else
{
if(!secondBestDone)
{
bfs(FEM, SEM);
secondBest = min(secondBest, - cleanAndAdd(SEM, FEM) + edges[i].fr );
if(secondBest == 0)
secondBestDone = 1;
}
}
}
}
int main()
{
//read();
int p, q, w;
int kases;
getint(kases);
while(kases--)
{
getint(N); getint(M);
edges.clear();
loop(i, M)
{
getint(p); getint(q); getint(w);
edges.pb(mp(w, mp(p, q)));
}
sort(all(edges));
for(int i=1; i<=N; i++) parent[i] = i, graph[i].clear();
MST();
secondBest += best;
cout<<best<<" "<<secondBest<<endl;
}
return 0;
}
UnLucky Codes 