naoya_t@topcoder

SRM477 Medium: PythTriplets

過去問 | 01:46 |

寝倒し回

• なんだ最大フローで解ける問題じゃん
  • GCJの問題でこういう系のなかった？
  • 最大マッチングを求める問題は、全てのメンバーを二部グラフの両側に置いて、可能な結合パターンのところに容量１のパイプを敷いて、ソースとシンクを別途設け、ソースから二部グラフの一方の全メンバーにそれぞれ容量１のパイプを、二部グラフのもう一方の全メンバーからシンクへそれぞれ容量１のパイプを敷き、ソースからシンクへの最大フローを求めればよい。
  • ２階調画像のノイズ消去に同様の手法が使えるのが面白いです
• あ。答えが２倍になってる。最後に２で割ればおｋ
• submitted
• 396.39 (15'22'')
• failed system test...
  • GCDチェック忘れてるし
  • もう馬鹿馬鹿馬鹿
  • gcd()いれたらpassed system test
  • こういう抜けた所はどうにかしたい...これも取れてればrating1700行けるところなのに
• 以下、通るコード。コメントアウトしてるgcd()の部分が抜け。
  • うわ。皆さんの日記みたらGCD忘れが意外に多い。ナカーマ＞＜

using namespace std;
typedef long long ll;
typedef vector<int> vi;
typedef vector<vector<int> > vvi;
typedef vector<string> vs;
typedef vector<long long> vll;
#define sz(a)  int((a).size())
#define pb  push_back
#define FOR(var,from,to) for(int var=(from);var<=(to);var++)
#define rep(var,n)  for(int var=0;var<(n);var++)
#define all(c)  (c).begin(),(c).end()
#define tr(c,i)  for(typeof((c).begin()) i=(c).begin(); i!=(c).end(); i++)
#define found(s,e)  ((s).find(e)!=(s).end())

vector<string> split(string str, int delim=' ')
{
  vector<string> result;

  const char *s = str.c_str();
  if (delim == ' ') {
    for (const char *p=s; *p; p++) {
      if (*p == delim) s++;
      else break;
    }
    if (!*s) return result;

    for (const char *p=s; *p; p++) {
      if (*p == delim) {
        if (s < p) {
          string a(s,p-s);
          result.push_back(a);
        }
        s = p + 1;
      }
    }
    if (*s) result.push_back(s);
  } else {
    for (const char *p=s; *p; p++) {
      if (*p == delim) {
        string a(s,p-s);
        result.push_back(a);
        s = p + 1;
        if (*s == '\0') result.push_back("");
      }
    }
    if (*s) result.push_back(s);
  }

  return result;
}

vector<int> map_atoi(vector<string> nums)
{
  vector<int> vals(nums.size());
  for (int i=nums.size()-1; i>=0; i--) vals[i] = atoi(nums[i].c_str());
  return vals;
}

string join(vector<string> strs, const string &delim="")
{
  int n=strs.size(); if (n==0) return "";
  stringstream ss;
  ss << strs[0];
  for(int i=1;i<n;i++) { ss << delim << strs[i]; }
  return ss.str();
}

#define infty 987654321
int maximumFlow(const vector<vector<int> >& capacity, int s, int t) {
  int w = capacity.size();
  // residual networks
  vector<vector<int> > resid(w, vector<int>(w,0));
  for(int j=0; j<w-1; ++j){
    for(int k=j+1; k<w; ++k){
      resid[j][k] = capacity[j][k];
      resid[k][j] = 0;
    }
  }
  // find another way
  for (int total=0; ;++total) {
    bool another_way = false;
    vector<int> prev(w, infty);
    queue<pair<int,int> > q; q.push(pair<int,int>(s,-1));
    while (!q.empty()) {
      pair<int,int> p = q.front();
      int node = p.first, prev_node = p.second;
      q.pop();
      prev[node] = prev_node;
      if (node==t) { another_way = true; break; }
      rep(i,w) {
        if (resid[node][i] == 0) continue;
        if (prev[i] < infty) continue;
        q.push(pair<int,int>(i,node));
      }
    }
    // no more ways
    if (!another_way) return total;
    for (int node=t; node!=s; node=prev[node]) {
      int prev_node = prev[node];
      resid[prev_node][node]--;
      resid[node][prev_node]++;
    }
  }
  return 0;
}

//ll gcd(ll m, ll n)
//{
//  if (m == 0 || n == 0) return 0;
//  if (m == 1 || n == 1) return 1;
//  if (m == n) return m;
//  while (1) {
//    if (m == 0) return n;
//    if (n == 0) return m;
//    if (m > n) m %= n; else n %= m;
//  }
//}

class PythTriplets {
 private:
  ll sq(ll zz){
    ll zd = (ll)sqrt((double)zz);
    return (zd*zd == zz);
  }
  bool pyth(ll x, ll y){
//  if(gcd(x,y)>1) return false;
    return sq(x*x + y*y);
  }
 public:
  int findMax(vector <string> stick) {
    vector<int> st=map_atoi(split(join(stick)));//1-999999 x 1-200
    int n=sz(st);
    int w = 1+n+n+1;
    vector<vector<int> > capacity(w, vector<int>(w,0));
    rep(i,n) capacity[0][1+i] = capacity[1+n+i][1+n+n] = 1;
    rep(i,n)rep(j,n){
      if(i==j)continue;
      if(pyth(st[i],st[j])) capacity[1+i][1+n+j]=1;
    }
    int maxflow = maximumFlow(capacity, 0, 1+n+n);
    return maxflow/2;
  }
};