問題文 http://poj.org/problem?id=3169蟻本で解説されてる問題。やっと理解した。不等式制約の双対をとると最短経路問題になる。 #include <iostream> #include <vector> #include <algorithm> #define MAX_V 1001 #define MAX_E 30000 #define INF (1<<29) using namespace std; struct </algorithm></vector></iostream>…

問題文 http://poj.org/problem?id=24551~Nの頂点があって、1からNの間をT回移動したい。 一度移動に使った辺は使用できない。 移動の時に使う辺のコストの最大値を最小化せよ。 二分探索+最大流。 二分探索で、移動に使用する辺の最大値を決め打ちする。 決…

問題文 http://poj.org/problem?id=2391n頭の牛とm個のフィールドがある。 フィールドにはそれぞれ小屋があり、入れる牛の数も決まっている。 また、フィールド同士は辺でつながっている。 辺には牛が通れる数の制限はない。 全ての牛が小屋に入ることを考え…

問題文 http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0122 dfsした。 #include<iostream> #include<vector> #include<algorithm> #include<cmath> using namespace std; vector<pair<int,int> >sp; int dx[12]={-1,0,1,2,2,2,1,0,-1,-2,-2,-2}; int dy[12]={-2,-2,-2,-1,0,1,2,2,2,1,0,-1}; int n</pair<int,int></cmath></algorithm></vector></iostream>…

問題文 http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0116典型問題。↓を参考にした。 http://algorithms.blog55.fc2.com/blog-entry-133.html #include<iostream> #include<vector> #include<stack> #include<algorithm> using namespace std; typedef pair<int,int> pii; char G[501][501];</int,int></algorithm></stack></vector></iostream>…

問題文 http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=2118数字が書いてあるグリッドが与えられる。 この数字の中から、4近傍に隣接しているもの同士をとらないように選んだとき選んだ数字の和を最大化せよ。 前の一行を覚えておくdp。 #include<iostream></iostream>…

問題文 http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=2488 区間dp。monge性を使わなくても通ってしまった。 dp[i][j]:=i~j番目までの点で木を作るときの最小コスト #include<vector> #include<iostream> #include<algorithm> #include<map> #include<set> #include<queue> #include<string> #include<cctype> </cctype></string></queue></set></map></algorithm></iostream></vector>…