#include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include //#include //#include //#include //#include //#include //#include //#include //#include //#include //#if __cplusplus >= 201103L //#include //#include //#include //#include // //#define cauto const auto& //#else //#endif using namespace std; typedef long long ll; typedef pair pii; typedef pair pll; typedef vector vint; typedef vector > vvint; typedef vector vll, vLL; typedef vector > vvll, vvLL; #define VV(T) vector > template void initvv(vector > &v, int a, int b, const T &t = T()){ v.assign(a, vector(b, t)); } template void convert(const F &f, T &t){ stringstream ss; ss << f; ss >> t; } #undef _P #define _P(...) (void)printf(__VA_ARGS__) #define reep(i,a,b) for(int i=(a);i<(b);++i) #define rep(i,n) reep((i),0,(n)) #define ALL(v) (v).begin(),(v).end() #define PB push_back #define F first #define S second #define mkp make_pair #define RALL(v) (v).rbegin(),(v).rend() #define DEBUG #ifdef DEBUG #define dump(x) cout << #x << " = " << (x) << endl; #define debug(x) cout << #x << " = " << (x) << " (L" << __LINE__ << ")" << " " << __FILE__ << endl; #else #define dump(x) #define debug(x) #endif #define LDcout(x,n) fixed< class MaxFlow_dinic{ public: struct edge{int to,reve;V cap;}; static const int MV = 1100; vector E[MV]; int itr[MV],lev[MV]; void add_edge(int x,int y,V cap,bool undir=false){ E[x].push_back((edge){y,(int)E[y].size(),cap}); E[y].push_back((edge){x,(int)E[x].size()-1,undir?cap:0}); } void bfs(int cur){ memset(lev,0xff,sizeof(lev)); queue q; lev[cur]=0; q.push(cur); while(q.size()){ int v=q.front(); q.pop(); for(__typeof(E[v].begin()) e=E[v].begin();e!=E[v].end();e++) if(e->cap>0&&lev[e->to]<0) lev[e->to]=lev[v]+1,q.push(e->to); } } V dfs(int from,int to,V cf){ if(from==to){ return cf; } for(;itr[from]cap>0&&lev[from]to]){ V f=dfs(e->to,to,min(cf,e->cap)); if(f>0){ e->cap-=f; E[e->to][e->reve].cap += f; return f; } } } return 0; } V maxflow(int from,int to){ V fl=0,tf; while(1){ bfs(from); if(lev[to]<0) return fl; memset(itr,0,sizeof(itr)); while((tf=dfs(from,to,numeric_limits::max()))>0) fl+=tf; } } }; void mainmain(){ int n; cin>>n; vint v(n); rep(i,n) cin>>v[i]; MaxFlow_dinic mf; int start = 200; int goal = 201; rep(i,n){ mf.add_edge(start,i,1); mf.add_edge(i+n,goal,1); } rep(i,n){ rep(j,n){ if(v[i]==j) continue; mf.add_edge(i,j+n,1); } } int t=mf.maxflow(start,goal); // cout<