DOC

my_graph

By William Sullivan,2014-06-02 03:07
8 views 0
graph graphviz jgraph s7 graph sola graph rgraph knowledge graph under graph intergraph evalgraph

目录

    Kruskal ................................................................................................................................ 1

    单点度限制生成树 ................................................................................................................. 4

    最小树形图 ............................................................................................................................. 8

    K短路 .............................................................................................................................. 12

    无向图最小环 ....................................................................................................................... 14

    强联通分量 ........................................................................................................................... 15

    双连通分量 ........................................................................................................................... 17

    带上下届可行流 ................................................................................................................... 19

    最小费用最大流 ................................................................................................................... 21

Kruskal

    #define ES 201000

    #define VS 101000

    #include

    using namespace std;

    int n, m;

    struct edge {

     int x, y, len;

    } es[ES];

    int f[VS];

    bool cmp(edge a, edge b) {

     return a.len

    }

    int getf(int x) {

     if (f[x]!=x)

     f[x]=getf(f[x]);

     return f[x];

    }

    int kruskal() {

     int ans=0, l=0;

     for (int i=1; i<=n; i++)

     f[i]=i;

     for (int p=1; p<=m; p++) {

     if (getf(es[p].x)!=getf(es[p].y)) {

     ans+=es[p].len;

     l++;

     if (l==n-1)

     return ans;

     f[f[es[p].x]]=f[es[p].y];

     }

     }

     return -1;

    }

    int main() {

     scanf("%d %d\n", &n, &m);

     for (int i=1; i<=m; i++)

     scanf("%d %d %d\n", &es[i].x, &es[i].y, &es[i].len);

     sort(es+1, es+m+1, cmp);

     printf("%d\n", kruskal());

     return 0;

    }

    次小生成树

    #define inf 1147483647 #define N 600

    #define VS N

    #define ES 800000

    #include

    #include

    #include

    #include

    using namespace std;

    int n, m;

    struct heapnode {

     int id, w;

     heapnode() {

     }

     heapnode(int _id, int _w) :

     id(_id), w(_w) {

     }

    };

    bool operator<(heapnode a, heapnode b) {

     return a.w>b.w;

    }

    struct edge {

     int to, w;

     edge *next;

    } edges[ES];

    int es=0;

    struct Graph {

     void ins(int x, int y, int w) {

     edge *t=&edges[++es];

     t->to=y;

     t->w=w;

     t->next=tail[x];

     tail[x]=t;

     mat[x][y]=min(mat[x][y], w);

     }

     Graph() {

     init();

     }

     void init() {

     memset(tail, 0, sizeof(tail));

     memset(mat, 127, sizeof(mat));

     }

     int prim();

     edge* tail[VS];

     int mat[VS][VS];

    } G;

    struct Tree {

     void ins(int x, int y, int w) {

     edge *t=&edges[++es];

     t->to=y;

     t->w=w;

     t->next=tail[x];

     tail[x]=t;

     }

     int sub_spaning_tree() {

     int ret=inf;

     for (int i=1; i<=n; i++) {

     int t=bfs(i);

     if (t

     ret=t;

     }

     return ret;

     }

     int bfs(int B) {

     int ret=inf;

     queue<int> Q;

     bool vis[VS];

     memset(vis, 0, sizeof(vis));

     Q.push(B);

     while (Q.empty()==false) {

     int t=Q.front();

     Q.pop();

     for (edge *p=tail[t]; p; p=p->next) {

     int to=p->to;

     if (!vis[to]) {

     W[B][to]=max(p->w, W[B][t]);

     if (ret>G.mat[B][to]-W[B][to]&&B!=t)

     ret=G.mat[B][to]-W[B][to];

     vis[to]=true;

     Q.push(to);

     }

     }

     }

     return ret;

     }

     void init() {

     memset(tail, 0, sizeof(tail));

     }

     Tree() {

     init();

     }

     edge* tail[VS];

     int W[N][N];

    } T;

void input() {

     G.init();

     T.init();

     scanf("%d %d", &n, &m);

     for (int i=1; i<=m; i++) {

     int x, y, w;

     scanf("%d %d %d", &x, &y, &w);

     G.ins(x, y, w);

     G.ins(y, x, w);

     }

}

int Graph::prim() {

     priority_queue Q;

     int dis[N];

     bool vis[N];

     int pre[N];

     int ret=0;

     memset(vis, 0, sizeof(vis));

     memset(dis, 127, sizeof(dis));

     Q.push(heapnode(1, 0));

     dis[1]=0;

     pre[1]=-1;

     for (int i=1; i<=n; i++) {

     heapnode t;

     Q.push(heapnode(0, 2147483647));

     for (t=Q.top(), Q.pop(); vis[t.id]; Q.top(), Q.pop())

     ;

     if (!t.id)

     return -1;

     if (pre[t.id]>0) {

     T.ins(pre[t.id], t.id, t.w);

     T.ins(t.id, pre[t.id], t.w);

     }

     vis[t.id]=true;

     ret+=t.w;

     for (edge *p=tail[t.id]; p; p=p->next) {

     int to=p->to;

     if (dis[to]>p->w) {

     dis[to]=p->w;

     Q.push(heapnode(to, p->w));

     pre[to]=t.id;

     }

     }

     }

     return ret;

    }

int main() {

     freopen("x.in", "r", stdin);

     input();

     int t=G.prim();

     int sT=T.sub_spaning_tree();

     cout<<"Cost: "<

     cout<<"Cost: ";

     if (sT==inf)

     cout<<-1<

     else

     cout<

     return 0;

    }

    单点度限制生成树

    //#define DE

    #define inf 1047483647

#define VS 40

    #define ES 800

    #include #include #include #include

    #include

    using namespace std;

    struct nameid {

     int operator[](string s) {

     if (list.find(s)!=list.end())

     return list[s];

     list[s]=++size; #ifdef DE

     Name[size]=s; #endif

     return size;

     }

     mapint> list;

     nameid() :

     size(0) {

     }

     int size;

    #ifdef DE

     string Name[VS]; #endif

    } ID;

    struct Tree {

     void ins(int x, int y, int w) {

     mat[x][y]=w;

     mat[y][x]=w;

     }

     void del(int x, int y) {

     mat[x][y]=-1;

     mat[y][x]=-1;

     }

     Tree() {

     memset(mat, -1, sizeof(mat));

     }

     int mat[VS][VS]; };

    struct t_edge {

     int x, y, w;

     t_edge() {

     }

     t_edge(int a, int b, int c) :

     x(a), y(b), w(c) {

     }

    };

    bool cmp(t_edge a, t_edge b) {

     return a.w}

    struct Graph {

     t_edge edges[ES];

     Tree subT;

     int mat[VS][VS];

     int lb[VS];

     bool vis[VS];

     bool used[VS];

     int f[VS];

     int Root;

     int lbs;

     int es;

     int minid, mindeta, minX, minY;

     int makelab() {

     int ret=0;

     lbs=0;

     memset(vis, false, sizeof(vis));

     mat[0][Root]=inf;

     mat[Root][0]=inf;

     for (int i=2; i<=ID.size; i++)

     if (!vis[i]) {

     int j=0;

     dfs(i, ++lbs, j);

     used[j]=true;

     subT.ins(Root, j, mat[Root][j]);

     ret+=mat[Root][j];

     }

     return ret;

     }

     void dfs(int id, int lab, int &minp) {

     if (mat[Root][id]>0&&mat[Root][id]

     minp=id;

     vis[id]=true;

     lb[id]=lab;

     for (int i=1; i<=ID.size; i++) {

     if (i==Root)

     continue;

     if (!vis[i]&&mat[id][i]>0)

     dfs(i, lab, minp);

     }

     }

     int gf(int x) {

     if (f[x]!=x)

     f[x]=gf(f[x]);

     return f[x];

     }

     int kruskal() {

     sort(edges+1, edges+1+es, cmp);

     int ret=0, cnt=0;

     for (int i=1; i<=ID.size; i++)

     f[i]=i;

     for (int i=1; i<=es; i++) {

     int x=edges[i].x, y=edges[i].y;

     if (x==Root||y==Root)

     continue;

     if (gf(x)!=gf(y)) {

     f[gf(x)]=gf(y);

     ret+=edges[i].w;

     subT.ins(x, y, edges[i].w);

     if (++cnt==ID.size-1-lbs)

     break;

     }

     }

     return ret;

     }

     void init() {

     memset(mat, -1, sizeof(mat));

     es=0;

     Root=ID["Park"];

     }

     void ins(int x, int y, int w) {

     mat[x][y]=w;

     mat[y][x]=w;

     edges[++es]=t_edge(x, y, w);

     }

     void dfs(int u, int pre, int maxwid, int w) {

     vis[u]=true;

     for (int i=1; i<=ID.size; i++) {

     if (!vis[i]&&subT.mat[u][i]>0&&i!=Root) {

     int tmaxwid=maxwid, tw=w, tpre=pre;

     if (mat[u][i]>w)

     tw=mat[u][i];

     if (tw>w) {

     tpre=u;

     tmaxwid=i;

     }

     if (mat[Root][i]>0&&mindeta>-tw+mat[Root][i]&&!used[i]) {

     minid=i;

     mindeta=-tw+mat[Root][i];

     minX=tpre;

     minY=tmaxwid;

     }

     dfs(i, tpre, tmaxwid, tw);

     }

     }

     }

     int Klimitspanningtree(int limT) {

     int ret, ans=makelab();

     ans+=kruskal();

     ret=ans;

     for (int k=lbs+1; k<=limT; k++) {

     memset(vis, false, sizeof(vis));

     mindeta=inf;

     for (int i=1; i<=ID.size; i++) {

     if (used[i])

     dfs(i, 0, 0, 0);

     }

     if (mindeta>=0)

     continue;

     subT.ins(Root, minid, mat[Root][minid]);

     subT.del(minX, minY);

     used[minid]=true;

     ans+=mindeta;

     if (ret>ans)

     ret=ans;

     }

     return ret;

     }

     Graph() {

     init();

     }

} G;

int main() {

     freopen("x.in", "r", stdin);

     int n, lim;

     cin>>n;

     for (int i=1; i<=n; i++) {

     string s1, s2;

     int w;

     cin>>s1>>s2>>w;

     G.ins(ID[s1], ID[s2], w);

     G.ins(ID[s2], ID[s1], w);

     }

     cin>>lim;

     cout<<"Total miles driven: "<

    #ifdef DE

     G.subT.show();

    #endif

     return 0;

    }

    最小树形图

    double const oo = 1e8;

    double g[103][103];

    int pre[103], vis[103], del[103]; int N, M;

    inline void update(double &x, double y) {

     if (y < x)

     x = y;

    }

double MinTreeGraph() {

     memset(del, 0, sizeof (del));

     double ret = 0;

     while (true) {

     int check = 1;

     for (int i = 2; i <= N; i++) {

     if (del[i])

     continue;

     pre[i] = i, g[i][i] = oo;

     for (int j = 1; j <= N; j++) {

     if (del[j])

     continue;

     if (g[j][i] < g[pre[i]][i])

     pre[i] = j;

     }

     }

     for (int i = 2; i <= N; i++) {

     if (del[i])

     continue;

     memset(vis, 0, sizeof (vis));

     int node = i;

     while (node != 1 && !vis[node]) {

     vis[node] = 1, node = pre[node];

     }

     if (node == 1)

     continue;

     check = 0;

     int t = node;

     ret += g[pre[node]][node];

     node = pre[node];

     while (node != t) {

     ret += g[pre[node]][node], del[node] = 1, node = pre[node];

     }

     for (int j = 1; j <= N; j++) {

     if (del[j])

     continue;

     if (g[j][t] != oo)

     g[j][t] = g[j][t] - g[pre[t]][t];

     }

     node = pre[t];

     while (node != t) {

     for (int k = 1; k <= N; k++) {

     if (del[k])

     continue;

     update(g[t][k], g[node][k]);

     if (g[k][node] != oo)

     update(g[k][t], g[k][node] - g[pre[node]][node]);

     }

     node = pre[node];

     }

     break;

     }

     if (check) {

     for (int i = 2; i <= N; i++) {

     if (del[i])

     continue;

     ret += g[pre[i]][i];

     }

     break;

     }

     }

     return ret;

    }

Dijkstra

    #define VS 101001

    #define ES 201001

    #define INT_MAX 0x7f7f7f7f

    #include

    #include

    #include

#include

    using namespace std;

    int dis[VS];

    int tail[VS];

    int pre[2*ES];

    int to[2*ES];

    int len[2*ES];

    int es=0;

    int n, m;

    struct qE {

     int len, idx;

     qE(int l, int i) :

     len(l), idx(i) {

     }

     qE() {

     }

    };

    bool operator <(const qE &a, const qE &b) {

     return a.len>b.len; }

    void addedge(int x, int y, int t) {

     pre[++es]=tail[x];

     len[es]=t;

     to[es]=y;

     tail[x]=es;

    }

    void init() {

     memset(pre, -1, sizeof(pre));

     memset(tail, -1, sizeof(pre)); }

    int dijkstra(int s, int t) {

     priority_queue Q;

     memset(dis, 127, sizeof(dis));

     Q.push(qE(0, s));

     dis[s]=0;

     while (!Q.empty()) {

     qE t;

     do {

     t=Q.top();

     Q.pop();

     } while (dis[t.idx]!=t.len&&!Q.empty());

     for (int p=tail[t.idx]; p>0; p=pre[p]) {

     if (dis[to[p]]>t.len+len[p]) {

     dis[to[p]]=t.len+len[p];

     Q.push(qE(dis[to[p]], to[p]));

     }

     }

     }

     if (dis[t]==INT_MAX)

     return -1;

     return dis[t];

    }

    int main() {

     init();

     scanf("%d %d", &n, &m);

     for (int i=1; i<=m; i++) {

Report this document

For any questions or suggestions please email
cust-service@docsford.com