Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- bool kun(int v){
- if(u[v]) return false;
- u[v] = 1;
- for(int i = 1; i <= n; ++i){
- if(c[v][i]) continue;
- if(!sat[i] || kun(sat[i])){
- sat[i] = v;
- return true;
- }
- }
- return false;
- }
- bool try_ven(){
- /// ->create null
- for(int i = 1; i <= n; ++i){
- int mx = INF;
- for(int j = 1; j <= n; ++j){
- mx = min(mx,c[i][j]);
- }
- ans+=mx;
- for(int j = 1; j <= n; ++j){
- c[i][j]-=mx;
- }
- }
- for(int j = 1; j <= n; ++j){
- int mx = INF;
- for(int i = 1; i <= n; ++i)
- mx = min(mx,c[i][j]);
- ans+=mx;
- for(int i = 1; i <= n; ++i)
- c[i][j]-=mx;
- }
- /// <- create null
- /// -> kun
- memset(rows,1,(n+1)*sizeof(rows[0]));
- memset(colls,0,(n+1)*sizeof(colls[0]));
- memset(sat,0,(n+1)*sizeof(sat[0]));
- for(int i = 1; i <= n; ++i){
- kun(i);
- memset(u,0,(n+1)*sizeof(u[0]));
- }
- int cnt = 0;
- for(int i = 1; i <= n; ++i){
- cnt += sat[i]>0;
- rows[sat[i]] = 0;
- }
- if(cnt==n) return true;
- /// <- kun
- bool any = true;
- ///just for fun
- while(any){
- any = false;
- for(int i = 1; i <= n; ++i){
- for(int j = 1; j <= n; ++j){
- if(rows[i] && !c[i][j] && !colls[j]){
- any = true;
- colls[j] = 1;
- }
- }
- }
- for(int i = 1; i <= n; ++i){
- for(int j = 1; j <= n; ++j){
- if(colls[j] && !rows[i] && !c[i][j] && sat[j] && i==sat[j]){
- any = true;
- rows[i] = 1;
- }
- }
- }
- }
- for(int i = 1; i <= n; ++i)
- rows[i] = !rows[i];
- int Min = INF;
- for(int i = 1; i <= n; ++i)
- for(int j = 1; j <= n; ++j)
- if(!colls[j] && !rows[i]) Min = min(Min,c[i][j]);
- for(int i = 1; i <= n; ++i){
- for(int j = 1; j <= n; ++j){
- if(!colls[j] && !rows[i]) c[i][j]-=Min;
- if(colls[j] && rows[i]) c[i][j]+=Min;
- }
- }
- ans+=Min;
- return false;
- }
- inline void vengerian(){
- while(!try_ven());
- ans = 0;
- /*/for(int i = 1; i <=n; ++i)
- for(int j = 1; j <= n; ++j)
- g[i][j] = maxm-g[i][j];*////if max
- for(int i = 1; i <= n; ++i){
- for(int j = 1; j <= n; ++j){
- if(sat[j]==i) ans+=g[i][j];
- }
- }
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement