(TIOJ) 2039 . AI-666 賺多少 [GREEDY]

https://tioj.ck.tp.edu.tw/problems/2039

先說，下面是82分的 N log N greedy解。

#include <bits/stdc++.h>
using namespace std;

typedef long long LL;

typedef pair<LL,LL> pii;
const int N = 2000006;
const LL INF = (1LL<<50);

LL a[N];

#define SZ(x) ((int)(x).size())
#define F first
#define S second

LL s[N];

int lc[N];
int rc[N];

LL cost[N];

bool dead[N];

int main ()
{
    int n,k;
    scanf("%d %d",&n,&k);
    vector<LL> v;
    for (int i=1;n>=i;i++)
    {
        scanf("%lld",&a[i]);
        if (i > 1)
        {
            int _ = a[i] - a[i-1];
            if (_ > 0)
            {
                if (v.empty())
                {
                    v.push_back(_);
                }
                else if (v.back() > 0)
                {
                    v[ SZ(v)-1 ] += _;
                }
                else if (v.back() < 0)
                {
                    v.push_back(_);
                }
            }
            else if (_ < 0)
            {
                if (v.empty()) ;
                else if (v.back() > 0)
                {
                    v.push_back(_);
                }
                else if (v.back() < 0)
                {
                    v[ SZ(v)-1 ] += _;
                }
            }
        }
    }
    if (!v.empty() && v.back() < 0) v.pop_back();
    long long tot=0;
    int b=0;
    for (int i:v)
    {
        if (i>0)
        {
            tot += i;
            ++b;
        }
    }
    if (b<=k)
    {
        printf("%lld\n",tot);
        return 0;
    }
    int nn = SZ(v);
    s[0] = s[nn+1] = 0;
    for (int i=1;nn>=i;i++)
    {
        s[i] = abs(v[i-1]);
        lc[i] = i-1;
        rc[i] = i+1;
        cost[i] = s[i];
    }
    priority_queue<pii,vector<pii>,greater<pii> > pq;
    for (int i=1;nn>=i;i++)
    {
        pq.push(make_pair(cost[i],i));
        //cout << "cost = " << cost[i] << " , i = " << i << endl;
    }
    while (!pq.empty() && b > k)
    {
        pii p=pq.top();
        pq.pop();
        if (dead[p.S]) continue;
        //cout << "p = (" << p.F<< " , " << p.S << " )" << endl;
        --b;
        tot -= p.F;
        int mid = p.S;
        int l = lc[mid];
        int r = rc[mid];
        cost[mid] = cost[l] + cost[r] - cost[mid];
        if (l != 0 && r != nn+1) pq.push(make_pair(cost[mid],mid));
        else dead[mid] = true;
        dead[l] = true;
        dead[r] = true;
        lc[mid] = lc[l];
        rc[mid] = rc[r];
        //cout << "l = " << l << " , r = " << r << endl;
        rc[ lc[l] ] = (r != nn+1?mid:nn+1);
        lc[ rc[r] ] = (l != 0?mid:0);
        /*
        for (int i=1;nn>=i;i++)
        {
            cout << "i = " << i << " , cost = " <<cost[i] << " , dead = " << dead[i] << " , lc = " << lc[i] << " , rc = " << rc[i] << endl;
        }*/

        //cout << endl << endl;
    }
    printf("%lld\n",tot);
}

(TIOJ) 1737 . [APIO '07] Backup [GREEDY]

https://tioj.ck.tp.edu.tw/problems/1737

一道很經典的greedy題，也是一道我很不想碰的題><

最後還是硬著頭皮寫出來惹。

這題跟這次JOI的candies很像喔XD。

附個題解網址：https://www.iarcs.org.in/inoi/online-study-material/problems/backup-soln.php#solution

#include <bits/stdc++.h>
using namespace std;

typedef long long LL;
const int N = 100006;

int lc[N],rc[N];
int val[N];

bool used[N];

struct Sagiri
{
    int b,e,cost;
    Sagiri(){}
    Sagiri(int _b,int _e,int _cost) : b(_b),e(_e),cost(_cost){}
};

bool operator<(const Sagiri &s1,const Sagiri &s2)
{
    return s1.cost > s2.cost;
}

bool operator>(const Sagiri &s1,const Sagiri &s2)
{
    return s1.cost < s2.cost;
}

int dis[N];

int main ()
{
    int n,k;
    scanf("%d %d",&n,&k);
    for (int i=1;n>=i;i++)
    {
        lc[i] = i-1;
        rc[i] = i+1;
    }
    priority_queue<Sagiri,vector<Sagiri> > pq;
    for (int i=1;n>=i;i++)
    {
        scanf("%d",&val[i]);
        //dis[i] --> i and i-1
        dis[i] = val[i] - val[i-1];
        if (i > 1)
        {
            int _ = val[i] - val[i-1];
            pq.push(Sagiri(i-1,i,_));
        }
    }
    int ans=0;
    while (!pq.empty() && k)
    {
        Sagiri s = pq.top();
        pq.pop();
        if (used[s.b] || used[s.e]) continue;
        //cout << "s = ( " << s.b << " , " << s.e << " , " <<s.cost << " ) " <<endl;
        --k;
        ans += s.cost;
        used[s.b] = used[s.e] = true;
        int bb = lc[s.b],ee = rc[s.e];
        rc[bb] = ee;
        lc[ee] = bb;
        dis[ee] = dis[ee] + dis[s.b] - dis[s.e];
        if (bb >= 1 && ee <= n && (!used[bb] && !used[ee]))
        {
            pq.push(Sagiri(bb,ee,dis[ee]));
        }
    }
    printf("%d\n",ans);
}

(TIOJ) 1934 . 旅行社大特價 [最小平均值環]

https://tioj.infor.org/problems/1934

今天學到一個很酷(?)的算法，就來記錄一下惹

當初看了題解看不太懂，在網路上查到 這份資料 後，就恍然大悟惹XD。

#include <bits/stdc++.h>
using namespace std;

typedef long long LL;
const int N = 1002;
const LL INF = (1LL<<41);
const LL INF2 = (1LL<<30);

LL adj[N][N];
LL dp[N][N];  //dp[i][j] --> from point 0 to point j threw i roads

int main()
{
    int n;
    scanf("%d",&n);
    for (int i=0;n+1>=i;i++)
    {
        for (int j=0;n+1>=j;j++)
        {
            dp[i][j] = INF;
        }
    }
    for (int i=1;n>=i;i++)
    {
        for (int j=1;n>=j;j++)
        {
            scanf("%lld",&adj[i][j]);
            if (!adj[i][j]) adj[i][j] = INF;
        }
    }
    for (int i=0;n>=i;i++)
    {
        adj[0][i] = 0;
        adj[i][0] = INF;
        if (i) dp[1][i] = 0;
    }
    for (int i=2;n+1>=i;i++)
    {
        //dp[i][j] --> i roads from 0 to j
        for (int j=0;n>=j;j++)
        {
            for (int k=0;n>=k;k++)
            {
                dp[i][j] = min(dp[i][j],dp[i-1][k] + adj[k][j]);
            }
        }
    }
    LL ansup = INF2, ansdown = 1;
    for (int i=1;n>=i;i++)
    {
        //go threw all possible i's
        LL tmpup = 0,tmpdown = 1;
        if (dp[n+1][i] == INF) continue;
        for (int j=1;n>=j;j++)
        {
            if (dp[j][i] == INF) continue;
            LL up = dp[n+1][i] - dp[j][i];
            LL down = n - j + 1;
            //up/down > tmpup/tmpdown
            if (up >= 0)
            {
                if (up * tmpdown > down * tmpup)
                {
                    tmpup = up;
                    tmpdown = down;
                }
            }
        }
        if (tmpup == 0) continue;
        //ansup/ansdown > tmpup / tmpdown
        if (ansup * tmpdown > ansdown * tmpup)
        {
            ansup = tmpup;
            ansdown = tmpdown;
        }
    }
    LL gcd = __gcd(ansup,ansdown);
    ansup /= gcd;
    ansdown /= gcd;
    if (ansup == INF2) puts("-1 -1");
    else printf("%lld %lld\n",ansup,ansdown);
}

(TIOJ) 1293 . I.送貨倉庫 [切比雪夫距離 --> 曼哈頓距離]

http://tioj.infor.org/problems/1293

坐標系的轉換(?)

在解這題之前，可以先去看看這裡。

有了上面那個之後，應該就不難了XDD。

#include <iostream>
#include <cstdio>
#include <vector>
#include <algorithm>
#include <utility>
using namespace std;

typedef long long LL;
typedef pair<LL,LL> pii;
const int N = 1e5 + 6;

LL x[N],y[N],t[N];

#define F first
#define S second
#define SZ(x) ((int)(x).size())

LL abss(LL x)
{
    if (x>0) return x;
    else return -x;
}

vector<pii> vx,vy;

vector<LL> solve(vector<pii> v)
{
    vector<LL> ret;
    LL sum=0;
    for (pii p:v)
    {
        sum += p.S;
    }
    LL pre=0;
    for (int i=0;SZ(v)>i;i++)
    {
        pre += v[i].S;
        if ((sum%2==1))
        {
            if (2*pre > sum)
            {
                ret.push_back(v[i].F);
                break;
            }
        }
        else
        {
            if (2*pre == sum)
            {
                ret.push_back(v[i].F);
                ret.push_back(v[i+1].F);
                ret.push_back(v[i].F+1);
                ret.push_back(v[i+1].F-1);
                break;
            }
            else if (2*pre > sum)
            {

                ret.push_back(v[i].F);
                break;
            }
        }
    }
    return ret;
}

#define __int128 long double

__int128 cal(LL x, LL y, __int128 ans)
{
    __int128 ret=0;
    for (pii p:vx)
    {
        ret += p.S * abss(x-p.F);
        if (ret > ans) return ret;
    }
    for (pii p:vy)
    {
        ret += p.S * abss(y-p.F);
        if (ret > ans) return ret;
    }
    return ret;
}

LL to_x(LL x,LL y)
{
    return (x+y)/2;
}

LL to_y(LL x,LL y)
{
    return (x-y)/2;
}

void update(__int128 &ans,LL &ansx, LL &ansy, LL x0,LL y0)
{
    if ((x0 + y0)&1) return;
    __int128 ret = cal(x0,y0,ans);
    if (ret < ans || ret == ans && make_pair(to_x(x0,y0),to_y(x0,y0)) < make_pair(ansx,ansy))
    {
        ans = ret;
        ansx = to_x(x0,y0);
        ansy = to_y(x0,y0);
    }
}

int main ()
{
    int n;
    while (scanf("%d",&n) != EOF)
    {
        vx.clear();
        vy.clear();
        for (int i=1;n>=i;i++)
        {
            scanf("%lld %lld %lld",&x[i],&y[i],&t[i]);
            vx.push_back(make_pair(x[i]+y[i],t[i]));
            vy.push_back(make_pair(x[i]-y[i],t[i]));
        }
        sort(vx.begin(),vx.end());
        sort(vy.begin(),vy.end());
        __int128 ans = (1LL<<62) + ( (1LL<<62)-1 );
        ans = ans * ans;
        LL ansx = (1LL<<62);
        LL ansy = (1LL<<62);
        vector<LL> retx=solve(vx),rety=solve(vy);
        int dx[9] = {-1,0,1,-1,0,1,-1,0,1},dy[9] = {-1,-1,-1,0,0,0,1,1,1};
        for (LL x0:retx)
        {
            for (LL y0:rety)
            {
                for (int i=0;9>i;i++)
                {
                    LL x=x0+dx[i],y=y0+dy[i];
                    update(ans,ansx,ansy,x,y);
                }
            }
        }
        printf("%lld %lld\n",ansx,ansy);
    }
}

(TIOJ) 1973 . 分群問題（Partition） [球球DP(?)]

http://tioj.infor.org/problems/1973

第一次成功克服心理恐懼，寫出類似這種的DP式子><

#include <bits/stdc++.h>
using namespace std;

typedef long long LL;
const LL mod = 1e9 +7;

const int N = 5006;

int dp[N][N];

int main ()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    char c;
    cin >> c;
    if (c=='U')
    {
        int n,k;
        cin >> n >> k;
        while (k--)
        {
            int x;
            cin >> x;
            n-=x;
        }
        dp[0][0] = 1;
        //i balls has j boxes
        for (int i=1;n>=i;i++)
        {
            for (int j=1;i>=j;j++)
            {
                if (i-j < 0) dp[i][j] = dp[i-1][j-1];
                else dp[i][j] = dp[i-1][j-1] + dp[i-j][j];
                dp[i][j] %= mod;
                //cout<<dp[i][j]<< ' ';
            }
            //cout<<endl;
        }
        LL sum = 0;
        for (int i=1;n>=i;i++)
        {
            sum += dp[n][i];
            sum %= mod;
        }
        cout << sum << endl;
    }
    else {
        int n,k;
        cin >> n >> k;
        dp[k][k] = 1;
        //i balls has j boxes
        for (int i=k;n>=i;i++)
        {
            for (int j=k;i>=j;j++)
            {
                if (i==k && j==k) continue;
                dp[i][j] = (dp[i-1][j-1] + dp[i-1][j]*1LL*j ) % mod;
                dp[i][j] %= mod;
            }
        }
        LL sum=0;
        for (int i=1;n>=i;i++)
        {
            sum += dp[n][i];
            sum %= mod;
        }
        cout << sum << endl;
    }
}

(TIOJ) 1042 . E.老問題 [各種KM]

http://tioj.infor.org/problems/1042

二分圖最大權匹配算法大集合(?)

法一：Min-Cost Max-Flow

#include <iostream>
#include <stdio.h>
#include <vector>
#include <utility>
#include <queue>
#include <cstring>
using namespace std;

typedef pair<int,int> pii;

struct CostFlow {
    int n,s,t;
    static const int MAX_N = 206;
    struct Edge {
        int to,cap,rev,cost;
    };
    vector<Edge> edg[MAX_N];
    void init(int _n,int _s,int _t) {
        n=_n;
        s=_s;
        t=_t;
        for (int i=0;n>=i;i++) {
            edg[i].clear();
        }
    }
    #define SZ(x) ((int)(x).size())
    void add_edge(int from,int to,int cap,int cost) {
        edg[from].push_back({to,cap,SZ(edg[to]),cost});
        edg[to].push_back({from,0,SZ(edg[from])-1,-cost});
    }
    const int INF = 1e9 +7;
    int dis[MAX_N],pre[MAX_N],pre_id[MAX_N];
    bool in_que[MAX_N];
    pii flow() {
        int cost=0,flow=0;
        while (true) {
            for (int i=0;n>=i;i++) {
                dis[i] = INF;
                in_que[i] = 0;
            }
            queue<int> que;
            que.push(s);
            dis[s] = 0;
            while (!que.empty()) {
                int t=que.front();
                que.pop();
                in_que[t] = false;
                int id=0;
                for (Edge e:edg[t]) {
                    if (e.cap >0 && dis[e.to] > dis[t] + e.cost) {
                        dis[e.to] = dis[t] + e.cost;
                        pre[e.to] = t;
                        pre_id[e.to] = id;
                        if (!in_que[e.to]) {
                            in_que[e.to]=1;
                            que.push(e.to);
                        }
                    }
                    id++;
                }
            }
            if (dis[t] == INF) break;
            if (dis[t] > 0) break;
            int mn_flow = INF;
            for (int i=t;i!=s;i=pre[i]) {
                mn_flow = min(mn_flow,edg[pre[i]][pre_id[i]].cap);
            }
            flow += mn_flow;
            cost += mn_flow * dis[t];
            for (int i=t;i!=s;i=pre[i]) {
                edg[pre[i]][pre_id[i]].cap -= mn_flow;
                edg[i][edg[pre[i]][pre_id[i]].rev].cap += mn_flow;
            }
        }
        return make_pair(flow,cost);
    }
} flow;

const int MAX_N = 1e2 + 6;

int a[MAX_N][MAX_N];

int main () {
    int n;
    while (scanf("%d",&n) != EOF) {
        if (!n) break;
        flow.init(2*n+2,0,2*n+1);
        for (int i=1;n>=i;i++) {
            for (int j=1;n>=j;j++) {
                scanf("%d",&a[i][j]);
                flow.add_edge(i,j+n,1,-a[i][j]);
            }
        }
        for (int i=1;n>=i;i++) {
            flow.add_edge(0,i,1,0);
        }
        for (int j=1;n>=j;j++) {
            flow.add_edge(j+n,2*n+1,1,0);
        }
        pii ret=flow.flow();
        printf("%d\n",-ret.second);
    }
}

法二：KM O(n^4)

#include <iostream>
#include <cstdio>
#include <vector>
#include <algorithm>
#include <cstring>
#include <utility>
#include <cmath>
#include <ctime>
#include <cstdlib>
#include <queue>
#include <stack>
#include <set>
#include <map>
using namespace std;

#define LL   long long
#define ld   long double
#define pii  pair<int,int>
#define pLL  pair<LL,LL>
#define vint vector<int>
#define vLL  vector<LL>
#define vpii vector<pii>

#define SZ(x) ((int)(x).size())
#define ALL(x) (x).begin(),(x).end()
#define F first
#define S second
#define MP make_pair
#define PB push_back

#define Si(x) scanf("%d",&(x));
#define Sii(x,y) scanf("%d %d",&(x),&(y));
#define Siii(x,y,z) scanf("%d %d %d",&(x),&(y),&(z));
#define Siiii(x,y,z,w) scanf("%d %d %d %d",&(x),&(y),&(z),&(w));
#define Siiiii(x,y,z,w,a) scanf("%d %d %d %d %d",&(x),&(y),&(z),&(w),&(a));
#define Siiiiii(x,y,z,w,a,b) scanf("%d %d %d %d %d %d",&(x),&(y),&(z),&(w),&(a),&(b));
#define SL(x) scanf("%lld",&(x));
#define SLL(x,y) scanf("%lld %lld",&(x),&(y));
#define SLLL(x,y,z) scanf("%lld %lld %lld",&(x),&(y),&(z));
#define SLLLL(x,y,z,w) scanf("%lld %lld %lld %lld",&(x),&(y),&(z),&(w));
#define SLLLLL(x,y,z,w,a) scanf("%lld %lld %lld %lld %lld",&(x),&(y),&(z),&(w),&(a));
#define SLLLLLL(x,y,z,w,a,b) scanf("%lld %lld %lld %lld %lld %lld",&(x),&(y),&(z),&(w),&(a),&(b));

#define Pi(x) printf("%d\n",(x));
#define Pii(x,y) printf("%d %d\n",(x),(y));
#define Piii(x,y,z) printf("%d %d %d\n",(x),(y),(z));
#define Piiii(x,y,z,w) printf("%d %d %d %d\n",(x),(y),(z),(w));
#define Piiiii(a,b,c,d,e) printf("%d %d %d %d %d\n",(a),(b),(c),(d),(e));
#define Piiiiii(a,b,c,d,e,f) printf("%d %d %d %d %d %d\n",(a),(b),(c),(d),(e),(f));
#define PL(x) printf("%lld\n",(x)*1LL);
#define PLL(x,y) printf("%lld %lld\n",(x)*1LL,(y)*1LL);
#define PLLL(x,y,z) printf("%lld %lld %lld\n",(x)*1LL,(y)*1LL,(z)*1LL);
#define PLLLL(x,y,z,w) printf("%lld %lld %lld %lld\n",(x)*1LL,(y)*1LL,(z)*1LL,(w)*1LL);
#define PLLLLL(a,b,c,d,e) printf("%lld %lld %lld %lld %lld\n",(a),(b),(c),(d),(e));
#define PLLLLLL(a,b,c,d,e,f) printf("%lld %lld %lld %lld %lld %lld\n",(a),(b),(c),(d),(e),(f));

#define Pi1(x) printf("%d",  (x));
#define PL1(x) printf("%lld",(x));
#define Pspace putchar(' ');
#define Pendl  puts("");

#define MEM0(x) memset( (x), 0, sizeof( (x) ) )
#define MEM1(x) memset( (x),-1, sizeof( (x) ) )
#define REP1(i,n)  for (int i = 1; (n) >= i ; ++i)
#define REP0(i,n)  for (int i = 0; (n) >  i ; ++i)

int myRnd() {
    return abs(  ((rand()<<15) | rand()) );
}

int myRnd(int L,int R) {
    return abs(( (rand()<<15)|rand() ) ) % (R-L+1) + L;
}

void Parr(int *arr,int L,int R) {
    for (int i=L;R>=i;i++) {
        printf("%d%c",arr[i]," \n"[i==R]);
    }
}

void Pvec(vint v) {
    for (int i=0;SZ(v)>i;i++) {
        printf("%d%c",v[i]," \n"[i==SZ(v)-1]);
    }
}

void Sarr(int *arr,int L,int R) {
    for (int i=L;R>=i;i++)
    {
        Si(arr[i]);
    }
}

const int N = 100 + 6;

LL a[N][N];

const LL INF = 1e15 + 7;

bool vx[N],vy[N];
LL Lx[N],Ly[N];
int match[N];

int n;

bool dfs(int i)
{
    vx[i] = 1;
    REP1(j,n)
    {
        if (!vy[j])
        {
            if (Lx[i] + Ly[j] == a[i][j])
            {
                vy[j] = 1;
                if (match[j] == -1 || dfs(match[j]))
                {
                    match[j] = i;
                    return true;
                }
            }
        }
    }
    return false;
}

int main () {
    srand(time(NULL));
    while (scanf("%d",&n) != EOF)
    {
        if (n==0) break;
        REP1(i,n)
        {
            REP1(j,n)
            {
                SL(a[i][j]);
                a[i][j] = max(a[i][j],0LL);
            }
        }
        MEM0(Lx);
        MEM0(Ly);
        REP1(i,n)
        {
            REP1(j,n)
            {
                Lx[i] = max(Lx[i],a[i][j]);
            }
        }
        MEM1(match);
        //Parr(Lx,1,n);
        //Parr(Ly,1,n);
        REP1(i,n)
        {
            //cout<<"I = "<<i<<endl;
            while (true)
            {
                MEM0(vx);
                MEM0(vy);
                if (dfs(i)) break;
                else
                {
                    LL mn = INF;
                    REP1(i,n)
                    {
                        if (!vx[i]) continue;
                        REP1(j,n)
                        {
                            if (vy[j]) continue;
                            mn = min(mn , Lx[i] + Ly[j] - a[i][j]);
                        }
                    }
                    if (mn < 0) break;
                    REP1(i,n)
                    {
                        if (vx[i]) Lx[i] -= mn;
                        if (vy[i]) Ly[i] += mn;
                    }
                }
            }
        }
        LL ans=0;
        //bool check=true;
        REP1(i,n)
        {
            if (a[ match[i] ][i] >= 0)
            {
                ans += a[ match[i] ][i];
            }
        }
        if (ans < 0) ans = 0;
        PL(ans);
    }
}

法三：KM O(n^3)

#include <iostream>
#include <cstdio>
#include <vector>
#include <algorithm>
#include <cstring>
#include <utility>
#include <cmath>
#include <ctime>
#include <cstdlib>
#include <queue>
#include <stack>
#include <set>
#include <map>
#include <cassert>
using namespace std;

#define LL   long long
#define ld   long double
#define pii  pair<int,int>
#define pLL  pair<LL,LL>
#define vint vector<int>
#define vLL  vector<LL>
#define vpii vector<pii>

#define SZ(x) ((int)(x).size())
#define ALL(x) (x).begin(),(x).end()
#define F first
#define S second
#define MP make_pair
#define PB push_back

#define Si(x) scanf("%d",&(x));
#define Sii(x,y) scanf("%d %d",&(x),&(y));
#define Siii(x,y,z) scanf("%d %d %d",&(x),&(y),&(z));
#define Siiii(x,y,z,w) scanf("%d %d %d %d",&(x),&(y),&(z),&(w));
#define Siiiii(x,y,z,w,a) scanf("%d %d %d %d %d",&(x),&(y),&(z),&(w),&(a));
#define Siiiiii(x,y,z,w,a,b) scanf("%d %d %d %d %d %d",&(x),&(y),&(z),&(w),&(a),&(b));
#define SL(x) scanf("%lld",&(x));
#define SLL(x,y) scanf("%lld %lld",&(x),&(y));
#define SLLL(x,y,z) scanf("%lld %lld %lld",&(x),&(y),&(z));
#define SLLLL(x,y,z,w) scanf("%lld %lld %lld %lld",&(x),&(y),&(z),&(w));
#define SLLLLL(x,y,z,w,a) scanf("%lld %lld %lld %lld %lld",&(x),&(y),&(z),&(w),&(a));
#define SLLLLLL(x,y,z,w,a,b) scanf("%lld %lld %lld %lld %lld %lld",&(x),&(y),&(z),&(w),&(a),&(b));

#define Pi(x) printf("%d\n",(x));
#define Pii(x,y) printf("%d %d\n",(x),(y));
#define Piii(x,y,z) printf("%d %d %d\n",(x),(y),(z));
#define Piiii(x,y,z,w) printf("%d %d %d %d\n",(x),(y),(z),(w));
#define Piiiii(a,b,c,d,e) printf("%d %d %d %d %d\n",(a),(b),(c),(d),(e));
#define Piiiiii(a,b,c,d,e,f) printf("%d %d %d %d %d %d\n",(a),(b),(c),(d),(e),(f));
#define PL(x) printf("%lld\n",(x)*1LL);
#define PLL(x,y) printf("%lld %lld\n",(x)*1LL,(y)*1LL);
#define PLLL(x,y,z) printf("%lld %lld %lld\n",(x)*1LL,(y)*1LL,(z)*1LL);
#define PLLLL(x,y,z,w) printf("%lld %lld %lld %lld\n",(x)*1LL,(y)*1LL,(z)*1LL,(w)*1LL);
#define PLLLLL(a,b,c,d,e) printf("%lld %lld %lld %lld %lld\n",(a),(b),(c),(d),(e));
#define PLLLLLL(a,b,c,d,e,f) printf("%lld %lld %lld %lld %lld %lld\n",(a),(b),(c),(d),(e),(f));

#define Pi1(x) printf("%d",  (x));
#define PL1(x) printf("%lld",(x));
#define Pspace putchar(' ');
#define Pendl  puts("");

#define MEM0(x) memset( (x), 0, sizeof( (x) ) )
#define MEM1(x) memset( (x),-1, sizeof( (x) ) )
#define REP1(i,n)  for (int i = 1; (n) >= i ; ++i)
#define REP0(i,n)  for (int i = 0; (n) >  i ; ++i)

int myRnd() {
    return abs(  ((rand()<<15) | rand()) );
}

int myRnd(int L,int R) {
    return abs(( (rand()<<15)|rand() ) ) % (R-L+1) + L;
}

void Parr(int *arr,int L,int R) {
    for (int i=L;R>=i;i++) {
        printf("%d%c",arr[i]," \n"[i==R]);
    }
}

void Pvec(vint v) {
    for (int i=0;SZ(v)>i;i++) {
        printf("%d%c",v[i]," \n"[i==SZ(v)-1]);
    }
}

void Sarr(int *arr,int L,int R) {
    for (int i=L;R>=i;i++)
    {
        Si(arr[i]);
    }
}

const int N = 100 + 6;

LL a[N][N];

const LL INF = 1e15 + 7;

bool vx[N],vy[N];
LL Lx[N],Ly[N];
int match[N];

int n;

LL slack_y[N];

bool dfs(int i,bool change = true)
{
    if (vx[i]) return false;
    vx[i] = 1;
    REP1(j,n)
    {
        LL val = Lx[i] + Ly[j] - a[i][j];
        if (!vy[j])
        {
            if (Lx[i] + Ly[j] == a[i][j])
            {
                vy[j] = 1;
                if (match[j] == -1 || dfs(match[j],change))
                {
                    if (change)match[j] = i;
                    return true;
                }
            }
            else
            {
                slack_y[j] = min(slack_y[j],val);
            }
        }
    }
    return false;
}

int main () {
    srand(time(NULL));
    while (scanf("%d",&n) != EOF)
    {
        if (n==0) break;
        REP1(i,n)
        {
            REP1(j,n)
            {
                SL(a[i][j]);
                a[i][j] = max(a[i][j],0LL);
            }
        }
        MEM0(Lx);
        MEM0(Ly);
        REP1(i,n)
        {
            REP1(j,n)
            {
                Lx[i] = max(Lx[i],a[i][j]);
            }
        }
        MEM1(match);
        //Parr(Lx,1,n);
        //Parr(Ly,1,n);
        REP1(i,n)
        {
            //cout<<"I = "<<i<<endl;
            REP1(i,n) slack_y[i] = INF;
            MEM0(vx);
            MEM0(vy);
            if (dfs(i)) continue;
            bool flag = true;
            while (flag)
            {
                LL mn = INF;
                REP1(j,n)
                {
                    if (!vy[j]) mn = min(mn,slack_y[j]);
                }
                REP1(i,n)
                {
                    if (vx[i]) Lx[i] -= mn;
                    if (vy[i]) Ly[i] += mn;
                    else slack_y[i] -= mn;
                }
                REP1(j,n)
                {
                    if (!vy[j] && slack_y[j] == 0)
                    {
                        vy[j] = 1;
                        if (match[j] == -1 || dfs(match[j],false))
                        {
                            flag = false;
                            break;
                        }
                    }
                }
            }
            MEM0(vx);
            MEM0(vy);
            assert(dfs(i));
        }
        LL ans=0;
        //bool check=true;
        REP1(i,n)
        {
            if (a[ match[i] ][i] >= 0)
            {
                ans += a[ match[i] ][i];
            }
        }
        if (ans < 0) ans = 0;
        PL(ans);
    }
}