問題
http://community.topcoder.com/stat?c=problem_statement&pm=10766&rd=14157
以下の条件を満たす３角形を考える。
・３辺a,b,cがすべて整数
・a^2+b^2=c^2
・a,bの最大公約数が1
また辺の集合が与えられ、この中からできるだけ多く(a,b)のペアを作りたい。
このとき、(a,b)のペアの最大数を求める。
解き方
a,bの最大公約数が1であるということは、片方が奇数で片方が偶数になる。
仮に両方とも偶数であれば最大公約数は2以上になり、
両方とも奇数であればa^2+b^2=c^2が成り立たない。
上記より奇数のグループと偶数のグループからペアの最大数を見つける問題になるので
２部マッチングが適用できる。
コード
using namespace std;
#define all(c) (c).begin(),(c).end()
#define FORE(i,d,e) for(int i=d;i<e;i++)
#define FOR(i,s,e) for (int i = int(s); i != int(e); i++)
#define FORIT(i,c) for (typeof((c).begin()) i = (c).begin(); i != (c).end(); i++)
#define ISEQ(c) (c).begin(), (c).end()
int edge[2600][2600],visited[2600],to[2600],ret,n;
class PythTriplets {
public:
bool dfs(int x){
if(x==-1)return true;
if(visited[x])return false;
visited[x]=true;
FORE(i,0,n){
if(edge[x][i]&&dfs(to[i])){
to[x]=i;
to[i]=x;
return true;
}
}
return false;
}
bool calc(){
bool ok=false;
memset(visited,0,sizeof(visited));
FORE(i,0,n){
if(to[i]==-1&&dfs(i)){
ret++;
ok=true;
}
}
return ok;
}
long long gcd(long long x,long long y){
return y ? gcd(y,x%y) : x;
}
bool ispair(long long a,long long b){
if(gcd(a,b)>1)return false;
long long c=sqrt((double)a*a+b*b);
return (a*a+b*b==c*c);
}
int findMax(vector<string> stick) {
vector<long long> t;
string str=accumulate(all(stick),string());
stringstream out(str);
for(long long x;out>>x;)t.push_back(x);
n=t.size();
memset(edge,0,sizeof(edge));
FORE(i,0,n)FORE(j,0,n)edge[i][j]=ispair(t[i],t[j]);
ret=0;
memset(to,-1,sizeof(to));
while(calc());
return ret;
}
};
#define all(c) (c).begin(),(c).end()
#define FORE(i,d,e) for(int i=d;i<e;i++)
#define FOR(i,s,e) for (int i = int(s); i != int(e); i++)
#define FORIT(i,c) for (typeof((c).begin()) i = (c).begin(); i != (c).end(); i++)
#define ISEQ(c) (c).begin(), (c).end()
int edge[2600][2600],visited[2600],to[2600],ret,n;
class PythTriplets {
public:
bool dfs(int x){
if(x==-1)return true;
if(visited[x])return false;
visited[x]=true;
FORE(i,0,n){
if(edge[x][i]&&dfs(to[i])){
to[x]=i;
to[i]=x;
return true;
}
}
return false;
}
bool calc(){
bool ok=false;
memset(visited,0,sizeof(visited));
FORE(i,0,n){
if(to[i]==-1&&dfs(i)){
ret++;
ok=true;
}
}
return ok;
}
long long gcd(long long x,long long y){
return y ? gcd(y,x%y) : x;
}
bool ispair(long long a,long long b){
if(gcd(a,b)>1)return false;
long long c=sqrt((double)a*a+b*b);
return (a*a+b*b==c*c);
}
int findMax(vector<string> stick) {
vector<long long> t;
string str=accumulate(all(stick),string());
stringstream out(str);
for(long long x;out>>x;)t.push_back(x);
n=t.size();
memset(edge,0,sizeof(edge));
FORE(i,0,n)FORE(j,0,n)edge[i][j]=ispair(t[i],t[j]);
ret=0;
memset(to,-1,sizeof(to));
while(calc());
return ret;
}
};