DOC

# my_graph

By William Sullivan,2014-06-02 03:07
7 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