(UVA) 11045 - My T-shirt suits me

https://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&category=24&problem=1986

flowing~~~

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

const int MAX_N = 106;
const int INF = 1e9 + 7;

struct Edge {
    int to,cap,rev;
};

Edge MP(int to,int cap,int rev) {
    return (Edge){to,cap,rev};
}

vector<Edge> edg[MAX_N];
int iter[MAX_N];
int level[MAX_N];

void add_edge(int from,int to,int cap) {
    edg[from].push_back(MP(to,cap,edg[to].size()));
    edg[to].push_back(MP(from,0,edg[from].size()-1));
}

void bfs(int s) {
    //cout<<"s = "<<s<<endl;
    memset(level,-1,sizeof(level));
    level[s]=0;
    queue<int> que;
    que.push(s);
    while (!que.empty()) {
        int t=que.front();
        //cout<<"t = "<<t<<endl;
        que.pop();
        int len=edg[t].size();
        for (int x=0;len>x;x++) {
            Edge e=edg[t][x];
            if(e.cap > 0 && level[e.to] < 0) {
                //cout<<"update = "<<e.to<<" , t = "<<t<<" val = "<<level[e.to]<<" , "<<level[t]<<endl;
                level[e.to] = level[t] + 1;
                que.push(e.to);
            }
        }
    }
}

int dfs(int v,int t,int f) {
    //cout<<"v = "<<v<<" , t = "<<t<<" , f = "<<f<<endl;
    if (v==t) return f;
    int len=edg[v].size();
    for(int &i=iter[v];i<len;i++) {
        Edge &e=edg[v][i];
        if (e.cap > 0 && level[v] < level[e.to]) {
            int d=dfs(e.to,t,min(f,e.cap));
            if (d>0) {
                e.cap -= d;
                edg[e.to][e.rev].cap += d;
                return d;
            }
        }
    }
    return 0;
}

int Dinic(int s,int t) {
    int flow = 0;
    while (true) {
        //cout<<"inn\n";
        bfs(s);
        //cout<<"innnnnnnn\n";
        if (level[t] < 0) break;
        memset(iter,0,sizeof(iter));
        int f;
        while ((f=dfs(s,t,INF)) > 0) {
            flow += f;
        }
        //cout<<"flow = "<<flow<<endl;
    }
    return flow;
}

int main () {
    map<string,int> mp;
    mp["XS"]=41;
    mp["S"]=42;
    mp["M"]=43;
    mp["L"]=44;
    mp["XL"]=45;
    mp["XXL"]=46;
    int T;
    scanf("%d",&T);
    while (T--) {
        int n,m;
        scanf("%d %d",&n,&m);
        for (int x=0;MAX_N>x;x++) {
            edg[x].clear();
        }
        for (int i=41;46>=i;i++) {
            add_edge(0,i,n/6);
        }
        for (int x=1;m>=x;x++) {
            string i,j;
            cin >> i >> j;
            add_edge(mp[i],x,1);
            add_edge(mp[j],x,1);
            add_edge(x,m+1,1);
        }
        //cout<<"innn\n";
        int ret=Dinic(0,m+1);
        if (ret == m) puts("YES");
        else puts("NO");
    }
}

(UVA) 259 - Software Allocation

https://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&category=24&problem=195

flow !

Note that the code is not the AC code(due to EOF issue)

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

const int MAX_N = 106;
const int INF = 1e9 + 7;

struct Edge {
    int to,cap,rev;
};

vector<Edge> edg[MAX_N];
int iter[MAX_N];
int level[MAX_N];
int ans[MAX_N];

void add_edge(int from,int to,int cap) {
    edg[from].push_back((Edge){to,cap,edg[to].size()});
    edg[to].push_back((Edge){from,0,edg[from].size()-1});
}

void BFS(int s) {
    memset(level,-1,sizeof(level));
    level[s] = 0;
    queue<int> que;
    que.push(s);
    while (!que.empty()) {
        int t=que.front();
        que.pop();
        int len=edg[t].size();
        for (int i=0;len>i;i++) {
            Edge &tmp=edg[t][i];
            if (tmp.cap >0 && level[tmp.to] < 0) {
                level[tmp.to] = level[t] + 1;
                que.push(tmp.to);
            }
        }
    }
}

int DFS(int v,int t,int f,int source) {
    if (v==t) return f;
    int len = edg[v].size();
    for (int &i=iter[v];i<len;i++) {
        Edge &tmp=edg[v][i];
        if (tmp.cap > 0 && level[v] < level[tmp.to]) {
            int d=DFS(tmp.to,t,min(f,tmp.cap),v);
            if (d>0) {
                tmp.cap -= d;
                edg[tmp.to][tmp.rev].cap += d;
                if ('0' <= v &&  v <= '9') {
                    ans[v] = source;
                }
                return d;
            }
        }
    }
    return 0;
}

int Dinic(int s,int t) {
    int flow=0;
    while (true) {
        BFS(s);
        if (level[t] < 0) break;
        memset(iter,0,sizeof(iter));
        int f;
        while ((f=DFS(s,t,INF,s)) > 0) {
            flow += f;
        }
    }
    return flow;
}

vector<string> v;

int main () {
    //freopen("output.txt","w",stdout);
    string s;
    while (getline(cin,s)) {
        if (s=="") {
            memset(ans,0,sizeof(ans));
            for (int x=0;MAX_N>x;x++) {
                edg[x].clear();
            }
            int sum=0;
            for (vector<string>::iterator iter=v.begin();iter!=v.end();iter++) {
                s=*iter;
                char c=s[0];
                int t=s[1]-'0';
                sum += t;
                add_edge(0,c,t);
                int tmp=3;
                while (s[tmp] != ';') {
                    add_edge(c,s[tmp],1);
                    //add_edge(s[tmp],1,1);
                    tmp++;
                }
            }
            for (int x='0';'9'>=x;x++) {
                add_edge(x,1,1);
            }
            //cout<<"innnn\n";
            int ret = Dinic(0,1);
            //cout<<"ret = "<<ret<<endl;
            if (ret == sum) {
                for (int x='0';'9'>=x;x++) {
                    printf("%c",(ans[x]==0?'_':char(ans[x])));
                }
                puts("");
            }
            else {
                puts("!");
            }
            v.clear();
        }
        else {
            v.push_back(s);
        }
    }
}

(UVA) 820 - Internet Bandwidth [Dinic flow]

https://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&category=&problem=761

flow 模板XD

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

const int MAX_N = 106;
const int INF = 1e9 + 7;

struct edge {
    int to,cap,rev;
};

vector<edge> G[MAX_N];
int level[MAX_N];
int iter[MAX_N];

void add_edge(int from,int to,int cap) {
    G[from].push_back((edge){to,cap,G[to].size()});
    G[to].push_back((edge){from,0,G[from].size()-1});
}

void BFS(int s) {
    memset(level,-1,sizeof(level));
    queue<int> que;
    level[s] = 0;
    que.push(s);
    while (!que.empty()) {
        int v=que.front();
        que.pop();
        int len=G[v].size();
        for (int i=0;len>i;i++) {
            edge &e=G[v][i];
            if (e.cap > 0 && level[e.to] < 0) {
                level[e.to] = level[v] + 1;
                que.push(e.to);
            }
        }
    }
}

int dfs(int v,int t,int f) {
    //cout<<"v  = " << v <<" , t = " <<t <<" , f = "<<f<<endl;
    if (v==t) return f;
    int len=G[v].size();
    for (int &i=iter[v]; i<len;i++) {
        edge &e=G[v][i];
        if (e.cap > 0 && level[v] < level[e.to]) {
            int d=dfs(e.to,t,min(f,e.cap));
            if (d>0) {
                e.cap -= d;
                G[e.to][e.rev].cap += d;
                //cout<<"innnnn\n";
                return d;
            }
        }
    }
    return 0;
}

int Dinic(int s,int t) {
    int flow = 0;
    for (;;) {
        BFS(s);
        if (level[t] < 0) return flow;
        memset(iter,0,sizeof(iter));
        int f;
        while ((f = dfs(s,t,INF)) > 0) {
            //cout<<"get f = "<<f<<endl;
            flow += f;
        }
    }
}

int main () {
    int n;
    int cases=0;
    while (scanf("%d",&n) != EOF) {
        if (n==0) return 0;
        int s,t,m;
        scanf("%d %d %d",&s,&t,&m);
        for (int x=0;n>=x;x++) {
            G[x].clear();
        }
        for (int x=1;m>=x;x++) {
            int i,j,k;
            scanf("%d %d %d",&i,&j,&k);
            add_edge(i,j,k);
            add_edge(j,i,k);
        }
        printf("Network %d\n",++cases);
        printf("The bandwidth is %d.\n\n",Dinic(s,t));
    }
}

(POJ) 2187 -- Beauty Contest [最遠對點，旋轉卡尺]

http://poj.org/problem?id=2187

#include <iostream>
#include <stdio.h>
#include <cmath>
#include <algorithm>
using namespace std;

const double eps = 1e-9;
const int MAX_N = 50006;

#define double int

double add(double a,double b) {
       /*if (a+b < eps * (abs(a) + abs(b))) return 0;
       else */return a+b;
}

struct P {
       double x,y;
       P() {}
       P(double _x,double _y) :x(_x),y(_y) {}
};

P operator+(const P p1,const P p2) {
                  return P(add(p1.x,p2.x),add(p1.y,p2.y));
}

P operator-(const P p1,const P p2) {
                  return P(add(p1.x,-p2.x),add(p1.y,-p2.y));
}

P operator*(double d,const P p1) {
                   return P(p1.x*d,p1.y*d);
}

double dot(P p1,P p2) {
       return add(p1.x*p2.x,p1.y*p2.y);
}

double cross(P p1,P p2) {
       return add(p1.x*p2.y,-p1.y*p2.x);
}

double dis(P p1,P p2) {
       return (p1.x-p2.x)*(p1.x-p2.x) + (p1.y-p2.y)*(p1.y-p2.y);
}

bool operator<(const P &p1,const P &p2) {
     return p1.x<p2.x || p1.x==p2.x && p1.y<p2.y;
}

P p[MAX_N];
P u[MAX_N],d[MAX_N];

int main () {
    int n;
    while (scanf("%d",&n) != EOF) {
          for (int x=0;n>x;x++) {
              int a,b;
              scanf("%d %d",&a,&b);
              p[x] = P(a,b);
          }
          sort(p,p+n);
          
          //cout<<"These points : \n";
          //for (int x=0;n>x;x++) cout<<p[x].x<<' '<<p[x].y<<endl;
          
          int ans=0;
          int szu=0,szd=0; //上凸包，下凸包 
          for (int x=0;n>x;x++) {
              while (szd>1 && cross(d[szd-2]-d[szd-1],d[szd-1]-p[x]) <= 0) szd--;
              while (szu>1 && cross(u[szu-2]-u[szu-1],u[szu-1]-p[x]) >= 0) szu--;
              u[szu++]=p[x];
              d[szd++]=p[x];
          }
          
          //cout<<"down to_bou\n";
          //for (int x=0;szd>x;x++) cout<<d[x].x<<' '<<d[x].y<<endl;
          
          //cout<<"up to_bou\n";
          //for (int x=0;szu>x;x++) cout<<u[x].x<<' '<<u[x].y<<endl;
          
          if (szu>=2) d[szd]=u[szu-2];
          
          for (int i=0,j=szu-1;i<szu && j>0;) {
              ans = max(ans,dis(d[i],u[j]));
              
              if (cross(d[i]-d[i+1],u[j]-u[j-1]) <= 0) i++;
              else j--;
          }
          
          printf("%d\n",ans);
    }
}

(UVA) 10245 - The Closest Pair Problem [最近點對]

https://uva.onlinejudge.org/index.php?option=onlinejudge&Itemid=99999999&page=show_problem&category=&problem=1186

作法我是參考 演算法筆記 。

#include <iostream>
#include <stdio.h>
#include <cmath>
#include <cstring>
#include <algorithm>
using namespace std;

const int MAX_N = 10006;
const double INF = 1e9 + 7;

struct P {
    double x,y;
    P() {}
    P(double _x,double _y) : x(_x),y(_y) {
        
    }
} p[MAX_N],tmp[MAX_N];

bool com_x(P p1,P p2) {
    return p1.x<p2.x || p1.x==p2.x && p1.y<p2.y;
}

bool com_y(P p1,P p2) {
    return p1.y<p2.y || p1.y==p2.y && p1.x<p2.x;
}

double dis(P p1,P p2) {
    return sqrt((p1.x-p2.x)*(p1.x-p2.x) + (p1.y-p2.y)*(p1.y-p2.y));
}

double f(int L,int R) {
    if (L>=R) return INF;
    int mid=(L+R)>>1;
    double d=min(f(L,mid),f(mid+1,R));
    
    int sz=0;  //let's count how many number is near middle line
    for (int x=mid;   x>=L && p[mid].x - p[x].x < d ;x--) tmp[sz++]=p[x];
    for (int x=mid+1; R>=x && p[x].x - p[mid+1].x<d ;x++) tmp[sz++]=p[x];
    
    sort(tmp,tmp+sz,com_y);
    
    for (int i=0;sz>i;i++) {
        for (int j=1;3>=j && i+j<sz;j++) {
            d = min(d,dis(tmp[i],tmp[i+j]));
        }
    }
    
    return d;
}

int main () {
    int n;
    while (scanf("%d",&n) != EOF) {
        if (!n) return 0;
        for (int x=1;n>=x;x++) {
            double a,b;
            scanf("%lf %lf",&a,&b);
            p[x] = P(a,b);
        }
        sort(p+1,p+n+1,com_x);
        double ans=f(1,n);
        if (ans >= 10000) puts("INFINITY");
        else printf("%.4f\n",ans);
    }
}

(POJ) 2187 -- Beauty Contest [凸包]

http://poj.org/problem?id=2187

to_bou : 凸包

#include <iostream>
#include <stdio.h>
#include <cmath>
#include <algorithm>
using namespace std;

const int MAX_N = 5e4 + 6;
const double eps = 1e-9;
const int INF = 1e9 + 7;

#define double int

double add(double a,double b) {
    /*if (a+b <= eps*(abs(a) + abs(b))) return 0;
    else */return a+b;
}

struct P {
    double x,y;
    P() {}
    P(double _x,double _y) : x(_x),y(_y) {
    }
};

P operator+(const P p1,const P p2) {
    return P(add(p1.x,p2.x),add(p1.y,p2.y));
}

P operator-(const P p1,const P p2) {
    return P(add(p1.x,-p2.x),add(p1.y,-p2.y));
}

P operator*(const double d,const P p) {
    return P(d*p.x,d*p.y);
}

double dot(const P p1,const P p2) {
    return add(p1.x*p2.x,p1.y*p2.y);
}

double cross(const P p1,const P p2) {
    return add(p1.x*p2.y,-p1.y*p2.x);
}

bool operator<(const P &p1,const P &p2) {
    return p1.x<p2.x || p1.x==p2.x && p1.y<p2.y;
}

P p[MAX_N];
P to_bou[MAX_N];

int dis(P p1,P p2) {
    return (p1.x-p2.x)*(p1.x-p2.x) + (p1.y-p2.y)*(p1.y-p2.y);
}

int main () {
    int n;
    while (scanf("%d",&n) != EOF) {
        for (int x=0;n>x;x++) {
            int a,b;
            scanf("%d %d",&a,&b);
            p[x] = P(a,b);
        }
        sort(p,p+n);
        //cout<<"P : \n";
//        for (int x=0;n>x;x++) {
//            cout<<p[x].x <<' ' << p[x].y<<endl;
//        }
        int sz=0;
        for (int x=0;n>x;x++) {  //down to_bou
            while (sz > 1 && cross(to_bou[sz-2]-to_bou[sz-1],to_bou[sz-1]-p[x])<=0) {
                sz--;
            }
            to_bou[sz++]=p[x];
        }
        //cout<<"TO BOU : \n";
//        for (int x=0;sz>x;x++) {
//            cout << to_bou[x].x<<' '<<to_bou[x].y<<endl;
//        }
        int tmp=sz;
        for (int x=n-2;x>=0;x--) {
            while (sz > tmp && cross(to_bou[sz-2]-to_bou[sz-1],to_bou[sz-1]-p[x])<=0) {
                sz--;
            }
            to_bou[sz++]=p[x];
        }
        int ans=0;
//        cout<<"TO BOU : \n";
        for (int x=0;sz>x;x++) {
//            cout << to_bou[x].x<<' '<<to_bou[x].y<<endl;
            for (int y=0;sz>y;y++) {
                ans = max(ans,dis(to_bou[x],to_bou[y]));
            }
        }
        printf("%d\n",ans);
    }
}

(POJ) 1127 -- Jack Straws [點的操作]

http://poj.org/problem?id=1127

裡面有一些有關點的操作

#include <iostream>
#include <stdio.h>
#include <cstring>
#include <cmath>
using namespace std;

const int MAX_N = 15;
const double eps = 1e-9;

double add(double a,double b) {
    if (abs(a+b) < eps * (abs(a) + abs(b))) return 0;
    else return a+b;
}

struct P {
    double x,y;
    P() {}
    P(double _x,double _y) : x(_x),y(_y) {
    }
};

P operator+(const P p1,const P p2) {
    return P(add(p1.x,p2.x),add(p1.y,p2.y));
}

P operator-(const P p1,const P p2) {
    return P(add(p1.x,-p2.x),add(p1.y,-p2.y));
}

P operator*(const P p1,const double d) {
    return P(p1.x*d,p1.y*d);
}

double dot(const P p1,const P p2) {
    return add(p1.x*p2.x , p1.y*p2.y);
}

double cross(const P p1,const P p2) {
    return add(p1.x*p2.y,-p1.y*p2.x);
}

bool on_seg(P p1,P p2,P q) {
    return cross(p1-q,p2-q) == 0 && dot(p1-q,p2-q)<=0;
}

P touch(P p1,P p2,P q1,P q2) {
    return p1 + (p2-p1)*(cross(q1-p1,q2-q1)/cross(p2-p1,q2-q1));
}

bool dp[MAX_N][MAX_N];
P p[MAX_N],q[MAX_N];

int main () {
    int n;
    while (scanf("%d",&n) != EOF) {
        if (!n) break;
        for (int x=1;n>=x;x++) {
            double a,b,c,d;
            scanf("%lf %lf %lf %lf",&a,&b,&c,&d);
            p[x] = P(a,b);
            q[x] = P(c,d);
        }
        for (int x=0;n>=x;x++) {
            for (int y=0;n>=y;y++) {
                dp[x][y] = false;
                if (x==y) dp[x][y]=true;
            }
        }
        for (int i=1;n>=i;i++) {
            for (int j=i+1;n>=j;j++) {
                bool ans=false;
                if (cross(p[i]-q[i],p[j]-q[j])==0) {  //pararell
                    ans |= on_seg(p[i],q[i],p[j]) || on_seg(p[i],q[i],q[j]);
                    ans |= on_seg(p[j],q[j],p[i]) || on_seg(p[j],q[j],q[i]);
                }
                else {
                    P ret=touch(p[i],q[i],p[j],q[j]);
                    ans = on_seg(p[i],q[i],ret) && on_seg(p[j],q[j],ret);
                }
                dp[i][j] = dp[j][i] = ans;
            }
        }
        for (int k=1;n>=k;k++) {
            for (int i=1;n>=i;i++) {
                for (int j=1;n>=j;j++) {
                    dp[i][j] = dp[i][j] || dp[i][k] && dp[k][j];
                }
            }
        }
        int a,b;
        while (scanf("%d %d",&a,&b) != EOF) {
            if (!a && !b) break;
            else {
                if (dp[a][b]) puts("CONNECTED");
                else puts("NOT CONNECTED");
            }
        }
    }
}