ACM図論常用テンプレート(自用)

21474 ワード

いつも自分のよく使うテンプレートを整理する时間を探して、自分で探しやすいです.図論には多くのアルゴリズムがあり,後で改善を期待している.
最小生成ツリー
kruskal

hdu 1233は、欲張りな方法で、まず配列を定義し、ソートしてセットを調べることもできます.

#include
using namespace std;
const int maxn = 20005;
struct Node
{
    int x,y,val;
    Node(){}
    Node(int a,int b,int c):x(a),y(b),val(c){}
    bool operator a.val;
    }
};
int B[maxn];
int Find(int n)
{
    return n == B[n] ? n:B[n]=Find(B[n]);
}
int main()
{
    // ios::sync_with_stdio(false);
    // cin.tie(0);
    int N = 0;
    while(scanf("%d",&N)&&N){
        priority_queue Q;
        int a,b,c;
        int T = N*(N-1)/2;
        for(int i=1;i<=T;i++){
            B[i] = i;
        }
        for(int i=1;i<=T;i++){
            scanf("%d%d%d",&a,&b,&c);
            Q.push(Node(a,b,c));
        }
        int cnt = 0;
        int ans = 0;
        while(!Q.empty()&&cnt

生成ツリー数
SPOJ-HIGH

#include
typedef long long LL;
typedef unsigned long long ULL;
typedef long double LD;
using namespace std;

#define MaxN 15
#define MaxM MaxN*MaxN

struct Matrix  
{  
    LL a[MaxN][MaxN];   
    LL* operator[](int x)  
    {  
        return a[x];  
    }  
    LL det(int n)  
    {    
        LL ret = 1;  
        for(int i = 1; i < n; i++)  
        {  
            for(int j = i + 1; j < n; j++)  
                while(a[j][i])  
                {  
                    LL tmp = a[i][i] / a[j][i];  
                    for(int k = i; k < n; k++) a[i][k] = (a[i][k] - a[j][k]*tmp) ;  
                    for(int k = i; k < n; k++) swap(a[i][k], a[j][k]);  
                    ret = -ret;  
                }  
            if(a[i][i] == 0) return 0;  
            ret = ret*a[i][i] ;  
        }  
        return ret;  
    }  
}; 

int n,m;
int main()
{
    int T;
    scanf("%d", &T);
    while(T--)
    {
        scanf("%d%d", &n, &m);
        Matrix G,ans;
        memset(ans.a,0,sizeof(ans.a));
        for(int i=0;i

primアルゴリズム
ほぼDijksraアルゴリズムと似ています

poj1258

#include
#include
#include
#include
using namespace std;
const int maxn = 105;
typedef pair pii;
int G[maxn][maxn];
int dis[maxn];
int N = 0;
bool vis[maxn];

int prim()
{
    int ans = 0;
    memset(dis,0x7f,sizeof(dis));
    memset(vis,0,sizeof(vis));
    priority_queue,greater > Q;
    Q.push(pii(0,0));
    dis[0] = 0;
    while(!Q.empty()){
        pii t = Q.top();
        Q.pop();
        int u = t.first;
        int v = t.second;
        if(vis[v]) continue;
        vis[v] = 1;
        ans += u;
        for(int i=0;i d&&!vis[i]){ //   dijkstra        
                    dis[i] = d;          // 
                    Q.push(pii(dis[i],i));
                }
            }
        }
    }
    return ans;
}

int main(int argc, char const *argv[])
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    while(cin >> N){
        for (int i = 0; i < N; i++)
        {
            for (int j = 0; j < N; j++)
            {
                cin >> G[i][j];
            }
        }
        cout << prim() << endl;
    }
    return 0;
}

さいたんらく
dijkstraアルゴリズム

poj 2387はvecotr隣接テーブルで図を表し、疎図優先キューバージョンのdijkstraアルゴリズムに適用される.

#include
#include
#include
#include
using namespace std;
const int maxn = 10005;
int T,N;
vector G[maxn];
vector D[maxn];
int dis[maxn];
const int inf = 1<<31;
typedef pair pii;

int dijkstra()
{
    memset(dis,10,sizeof(dis));
    bool vis[maxn];
    memset(vis,0,sizeof(vis));
    priority_queue,greater > Q;
    Q.push(pii(0,1));
    while(!Q.empty()){
        pii t = Q.top();
        Q.pop();
        int d = t.first;
        int a = t.second;
        if(vis[a])continue;
        vis[a] = 1;
        for(int i=0;i di + d){
                dis[j] = di + d;
                Q.push(pii(dis[j],j));
            }
        }
    }
    return dis[N];
}

int main()
{
    cin >> T >> N;
    int a,b,c;
    for(int i=0;i> a >> b >> c;
        G[a].push_back(b);
        G[b].push_back(a);
        D[a].push_back(c);
        D[b].push_back(c);
    }
    cout << dijkstra() << endl;

    return 0;
}

bellman_fordアルゴリズム

poj 3259前M辺は双方向辺で、後W辺は一方向辺で、それから直接bellman_fordアルゴリズムは負のループを判定します(自分でspfaで負のループの結果WAを判定して、テストデータカードspfaなのか私spfaが書き間違えたのか分かりません).

#include
#include
#include
#include
#include
using namespace std;
const int maxn = 1005;
typedef pair pii;
int dis[maxn];
int N,M,W;
int k=0;

struct Edge 
{
    int to,from,cost;
};
Edge E[5000];

bool bellman_Ford()
{
    memset(dis,0,sizeof(dis));
    for(int i=1;i<=N;i++){
        for(int j=0;j dis[e.from] + e.cost){
                dis[e.to] = dis[e.from] + e.cost;
                if(i==N) return false;
            }
        }
    }
    return true;
}

int main(int argc, char const *argv[])
{
    int T = 0;
    cin >> T;
    while(T--){
        cin >> N >> M >> W;
        k = 0;
        int a,b,c;
        for(int i=0;i> E[k].from >> E[k].to >> E[k].cost;
            E[k+1].from = E[k].to;
            E[k+1].to = E[k].from;
            E[k+1].cost =  E[k].cost;
            k += 2;
        }
        for(int i=0;i> E[k].from >> E[k].to >> E[k].cost;
            E[k].cost = -E[k].cost;
            k++;
        }
        bool ok = bellman_Ford();
        if(ok){
            cout << "NO" <<  endl;
        }else{
            cout << "YES" << endl;
        }
    }
    return 0;
}

SPFAアルゴリズム
poj2240

#include
#include
#include
#include
#include
#include
#include
#include
using namespace std;
typedef long long ll;
typedef pair pii;
typedef pair PII;
const int maxn = 105;
const int maxm = 1e6+5;
const int inf = 1<<30;
struct Edge 
{
    int from,to;
    double cost;
    Edge(){}
    Edge(int a,int b,double c):from(a),to(b),cost(c){}
};
Edge E[maxm];
int N,M;
vector G[maxn];
map money;
double dis[maxn];
int vis[maxn],p[maxn],cnt[maxn];

bool spfa()
{
    queue Q;
    memset(vis,0,sizeof(vis));
    memset(cnt,0,sizeof(cnt));
    vis[0] = 1;
    for(int i=0;i N)return false;
                }
            }
        }
    }
    return true;
}

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    int Case = 1;
    while(cin >> N,N){
        money.clear();
        string s;
        for(int i=0;i> s;
            money[s] = i;
            G[i].clear();
        }
        cin >> M;
        double t;
        string s2;
        for(int i=0;i> s >> t >> s2;
            int f = money[s],to = money[s2];
            E[i] = Edge(f,to,t);
            G[f].push_back(i);
        }
        bool ok = spfa();
        cout << "Case "<< Case++ << ": ";
        if(!ok){
            cout << "Yes" << endl;
        }else{
            cout << "No" << endl;
        }
    }
    
    return 0;
}

Flodyアルゴリズム

for (int i = 0; i < n; i++) {   //      0  
    for (int j = 0; j < n; j++)  
        scanf("%lf", &dis[i][j]);  
}  
for (int k = 0; k < n; k++) {  
    for (int i = 0; i < n; i++) {  
        for (int j = 0; j < n; j++) {  
            dis[i][j] = min(dis[i][j], dis[i][k] + dis[k][j]);  
        }  
    }
}

ネットワークフロー
ぞうこうろアルゴリズム

ニンニク課排水テンプレート問題EdmondsKarpは二分図の最大基数マッチングにも使用でき、二分図の左側後右側にノードを追加し、二分図の両側のノードに接続すればよい.

#include 

using namespace std;
const int maxn = 205;
const int INF = 1<<30;
struct Edge
{
    int from,to,cap,flow;
    Edge(int u,int v,int c,int f):from(u),to(v),cap(c),flow(f){}
};

struct Dinic        //  
{
    int n,m,s,t;
    vector edges;
    vector G[maxn];
    bool vis[maxn];
    int d[maxn];
    int cur[maxn];

    void init(int n){
        for(int i=0;i Q;
        Q.push(s);
        d[s] = 0;
        vis[s] = 1;
        while(!Q.empty()){
            int x = Q.front();
            Q.pop();
            for(int i=0;i e.flow){
                    vis[e.to] = 1;
                    d[e.to] = d[x]+1;
                    Q.push(e.to);
                }
            }
        }
        return vis[t];
    }

    int DFS(int x,int a){
        if(x==t || a==0)return a;
        int flow = 0,f;
        for(int &i=cur[x];i0){
                e.flow += f;
                edges[G[x][i]^1].flow -= f;
                flow += f;
                a -= f;
                if(a==0)break;
            }
        }
        return flow;
    }

    int Maxflow(int s,int t){
        this->s = s,this->t = t;
        int flow = 0;
        while(BFS()){
            memset(cur,0,sizeof(cur));
            flow += DFS(s,INF);
        }
        return flow;
    }
    
};

struct EdmondsKarp
{
    int n,m;
    vector edges;
    vector G[maxn];
    int a[maxn];
    int p[maxn];

    void init(int n){
        for(int i=0;i Q;
            Q.push(s);
            a[s] = INF;
            while(!Q.empty()){
                int x = Q.front();Q.pop();
                for(int i=0;ie.flow){
                        p[e.to] = G[x][i];
                        a[e.to] = min(a[x],e.cap-e.flow);
                        Q.push(e.to);
                    }
                }
                
                if(a[t]) break;
            }
            if(!a[t])break;
            for(int u=t;u!=s;u=edges[p[u]].from){
                edges[p[u]].flow += a[t];
                edges[p[u]^1].flow -= a[t];
            }
            flow += a[t];
        }
        return flow;
    }
};

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    int n,m;
    cin >> n >> m;
    EdmondsKarp s;
    int a,b,c;
    for(int i=0;i> a >> b >>c;
        s.AddEdge(a,b,c);
    }
    cout << s.Maxflow(1,m) <

最小費用最大フロー
所与の流量、最小の費用を求めます

poj2135

#include
using namespace std;
typedef long long ll;
typedef pair pii;
typedef pair PII;
const int INF = 0x3f3f3f3f;

const int maxn = 1005;
struct Edge{
    int to,cap,cost,rev;
};

int V;
vector G[maxn];
int dis[maxn];
int prevv[maxn],preve[maxn];

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

int min_cost_flow(int s,int t,int f)
{
    int res = 0;
    while(f>0){
        memset(dis,0x3f,sizeof(dis));
        dis[s] = 0;
        bool update = true;
        while(update){
            update = false;
            for(int v = 0;v < V;v++){
                if(dis[v]==INF)continue;
                for(int i=0;i 0&& dis[e.to] > dis[v] + e.cost){
                        dis[e.to] = dis[v] + e.cost;
                        prevv[e.to] = v;
                        preve[e.to] = i;
                        update = true;
                    }
                }
            }
        }
        if(dis[t]==INF){
            return -1;
        }
        int d = f;
        for(int v = t;v!=s;v=prevv[v]){
            d = min(d,G[prevv[v]][preve[v]].cap);
        }
        f -= d;
        res += d*dis[t];
        for(int v=t;v!=s;v=prevv[v]){
            Edge& e = G[prevv[v]][preve[v]];
            e.cap -= d;
            G[v][e.rev].cap += d;
        }
    }
    return res;
}


int main(int argc, char const *argv[])
{
    int N,M;
    int a,b,c;
    scanf("%d %d",&N,&M);
    V = N;
    for(int i=0;i

流量が最大の流れを出力する時、最小の費用を求めます

#include
using namespace std;
typedef long long ll;
const int INF = 1<<30;

const int maxn = 10005;
struct Edge{
    int from ,to,cap,flow,cost;
    Edge(int u,int v,int c,int f,int w):from(u),to(v),cap(c),flow(f),cost(w){}
};

struct MCMF{
    int n,m;
    vector edges;
    vector G[maxn];
    int inq[maxn];  //      
    int d[maxn];    //Bellman-Ford
    int p[maxn];    //    
    int a[maxn];    //    

    void init(int n)
    {
        this-> n = n;
        for(int i=0;i Q;
        Q.push(s);
        while(!Q.empty()){
            int u = Q.front();Q.pop();
            inq[u] = 0;
            for(int i=0;i e.flow && d[e.to] > d[u] + e.cost){
                    d[e.to] = d[u] + e.cost;
                    p[e.to] = G[u][i];
                    a[e.to] = min(a[u],e.cap - e.flow);
                    if(!inq[e.to]){
                        Q.push(e.to);
                        inq[e.to] = 1;
                    }
                }
            }
        }
        if (d[t] == INF)
            return false;
        flow += a[t];
        cost += (ll)(d[t] * a[t]);
        int u = t;
        while (u != t){
            edges[p[u]].flow += a[t];
            edges[p[u] ^ 1].flow -= a[t];
            u = edges[p[u]].from;
        }

        return true;
    }

    int MincostMaxflow(int s,int t,ll& cost){
        int flow = 0;cost = 0;
        while(BellmanFord(s,t,flow,cost));
        return flow;
    }
};

二分図
二分図判定(クロス染色)

leetcode 886

static int speed_up = []() {
     ios::sync_with_stdio(false);
     cin.tie(nullptr);
     return 0;
 }();
const int MAX_N = 2005;
int V;
vector G[MAX_N];

int color[MAX_N];
 
bool dfs(int v, int c)
{
    color[v] = c; 
    for(int i = 0; i < G[v].size(); i++)
    {
        int j = G[v][i];
        if(color[j] == c)
            return false;
        if(color[j] == 0 && !dfs(j, -c))
            return false;
    }
    return true;
}
 
bool solve()
{
    for(int i = 1; i <= V; i++)
    {
        if(color[i] == 0)
        {
            if(!dfs(i,1))
            {
                
                return false;
            }
        }
    }
    return true;
}


class Solution {
public:
    bool possibleBipartition(int N, vector>& dislikes) {
        V = N;
        for(int i=0;i<=N;i++){
            G[i].clear();
        }
       memset(color,0,sizeof(color));
        for(int i=0;i

最大照合
poj3941

#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
using namespace std;
typedef long long ll;
typedef pair pii;
typedef pair PII;
const int maxn = 1005;
vector G[maxn];
int match[maxn];
int used[maxn];
int V;

void add_edge(int u,int v)
{
    G[u].push_back(v);
    G[v].push_back(u);
}

bool dfs(int v)
{
    used[v] = true;
    for(int i=0;i> N >> K;
    int a,b;
    V = 2*N;
    for(int i=0;i> a >> b;
        add_edge(a,b+N);
    }

    cout << bitpartite_match() << endl;
    
    return 0;
}

無方向エッジカットポイントと二重連通成分

uva315

#include 
using namespace std;
#define mclear(x) memset((x), 0, sizeof((x)))
typedef pair pii;
const int MAX = 5100;
int n, m, deep;
vector path[MAX];
int vis[MAX], low[MAX];
vector cutpoint; //  
vector bridge;   //  , 
int nbcc;             //      
stack order;
vector bcc[MAX]; //     

void dfs(int pos, int father)
{
    int i, j, total = 0;
    bool cut = false;
    int reback = 0; //     
    vis[pos] = low[pos] = deep++;
    int ls = path[pos].size();
    for (j = 0; j < ls; j++)
    {
        i = path[pos][j];
        if (i == father)
            reback++;
        if (vis[i] == 0)
        {
            pii e(pos, i);
            order.push(e);
            dfs(i, pos);
            if (low[i] >= vis[pos])
            {
                nbcc++;
                bcc[nbcc].clear();
                pii r;
                do
                {
                    r = order.top();
                    order.pop();
                    bcc[nbcc].push_back(r.second);
                } while (e != r);
                bcc[nbcc].push_back(r.first);
            }
            total++;
            low[pos] = min(low[i], low[pos]);
            if ((vis[pos] == 1 && total > 1) ||
                (vis[pos] != 1 && low[i] >= vis[pos]))
                cut = true;
            if (low[i] > vis[pos])
                bridge.push_back(e);
        }
        else if (i != father)
        {
            low[pos] = min(vis[i], low[pos]);
        }
    }
    if (reback > 1)
        low[pos] = min(low[pos], vis[father]);
    if (cut)
        cutpoint.push_back(pos);
}
void find_cut()
{
    int i;
    mclear(vis);
    mclear(low);
    cutpoint.clear();
    bridge.clear();
    nbcc = 0;
    while (!order.empty())
        order.pop();
    for (i = 1; i <= n; i++)
    {
        if (vis[i] == 0)
        {
            deep = 1;
            dfs(i, -1);
        }
    }
}

int main()
{
    while (~scanf("%d", &n) && n)
    {
        int a = 0;
        char c;
        vector vet;
        for (int i = 0; i <= n; i++)
        {
            path[i].clear();
        }
        int u = 0;
        while (scanf("%d", &u) && u)
        {
            while (scanf("%c", &c)&&c==' ')
            {
                scanf("%d",&a);
                path[u].push_back(a);
                path[a].push_back(u);
            }
        }
        find_cut();
        cout << cutpoint.size() << endl;
    }

    return 0;
}

きょうれんぞくぶん
SCCのTarjanアルゴリズム

poj1236

#include
#include
#include
#include
#include
#include
#include

using namespace std;
const int maxn = 105;
vector G[maxn];
bool M[maxn][maxn];
int pre[maxn],lowlink[maxn],sccno[maxn],dfs_clock,scc_cnt;
int out[maxn],in[maxn];
stack S;

int dfs(int u)
{
    pre[u] = lowlink[u] = ++dfs_clock;
    S.push(u);
    for(int i=0;i> N;
    int a = 0;
    for(int i=1;i<=N;i++){
        while(cin >> a&&a){
            G[i].push_back(a);
            M[i][a] = 1;
        }
    }
    
    find_scc(N);

    return 0;
}

転載先:https://www.cnblogs.com/django-lf/p/9717223.html

SQL Server疑い、不審、リカバリ中

SQL Server SQL文データベースを空にします(スキーマを含む場合)