《浅谈图论模型的建立与应用》-白红宇

《浅谈图论模型的建立与应用》

阅读量：6115 次

发布时间：2019-06-21

本文共 5232 字，大约阅读时间需要 17 分钟。

图论的建模，就是要抓住问题的本质，把问题抽象为点、边、权的关系。

Place the Robots (ZOJ 1654)

方案一：只关心空地与空地之间的联系，发生冲突的节点，连一条边，转换为求最大独立集。时间复杂度为：n*2^n

方案二：将所有横向方块，纵向方块分成X,Y部分，每个方块只能放一个机器人，那么有冲突的方块连一条边，问题转换为求最大匹配，最大匹配=最大流。

Source Code:

#include 
    
     #include 
     
      #include 
      
       #include 
       
        #include 
        
         #include 
         
          using namespace std;const int maxn = 1250;const int INF = 0x3f3f3f3f;int n,m;char maps[maxn][maxn];int col[maxn][maxn],row[maxn][maxn];int head[maxn*maxn];struct Edge{ int to; int next;} edges[maxn];int cnt;void add(int u,int v){ edges[cnt].to = v; edges[cnt].next = head[u]; head[u] = cnt++;}bool vis[maxn];int match[maxn];bool dfs(int u) { for(int i=head[u];~i;i=edges[i].next) { int v = edges[i].to; if(!vis[v]) { vis[v] = 1; if(match[v]==-1||dfs(match[v])) { match[v] = u; return true; } } } return false;}int R,C;int solve() { int num = 0; memset(match,-1,sizeof(match)); for(int i=0;i
          
           =0) { if(maps[i][tmp]!='#') { row[i][tmp] = R; tmp--; } else break; } while(j
           
            =0) { if(maps[tmp][j]!='#') { col[tmp][j] = C; tmp--; } else break; } while(i

差分约束：

x_1-x_2<=b_1

x_2-x_3<=b_2

x_3-x_4<=b_3

x_4-x_5<=b_4

\to x_1-x_5<=4\tag{1}

如果存在负环：

x_5-x_1<=-5\tag{2}

(1)(2)相加

0<=-1\tag{3}

无解，在图上表示，及存在负环。

#include 
    
     using namespace std;const int maxn = 30;int r[maxn];int t[maxn];struct Edge {    int from,to,dist;};struct BellmanFord {    int n,m;    vector
     
       edges;    vector
      
        G[maxn];    bool inq[maxn];    int d[maxn];    int p[maxn];    int cnt[maxn];    void init(int n) {        this->n = n;        for(int i=0;i

Q; memset(inq,0,sizeof(inq)); memset(cnt,0,sizeof(cnt)); for(int i=0;i

d[u]+e.dist) { d[e.to] = d[u] + e.dist; p[e.to] = G[u][i]; if(!inq[e.to]) { Q.push(e.to); inq[e.to] = true; if(++cnt[e.to]>n) return true; } } } } return false; }}sol;void build(int ans) { sol.init(25); for(int i=1;i<=24;i++) { sol.addEdge(i-1,i,t[i]); sol.addEdge(i,i-1,0); } for(int i=8;i<=24;i++) sol.addEdge(i,i-8,-r[i]); for(int i=1;i<8;i++) sol.addEdge(i,24+i-8,ans-r[i]); sol.addEdge(24,0,-ans);}int main(){ freopen("in.txt","r",stdin); int tt; scanf("%d",&tt); for(int z=0;z

>1; build(mid); if(sol.negativeCycle()) { ans = mid; r = mid-1; } else l = mid+1; } printf("%d\n",ans); } return 0;}

本题的卡片总数有十万之多，而最终要选取的卡片数不超过100张。如果在构图之前，把没有用的卡片先删掉，必将大大提高效率。

什么样的卡片是没有用的呢？

先考虑第一种能力的选取：如果把全部卡片按第一种能力值从大到小排序，显然我们应该尽量从前面选A张出来，由于每张卡片只能使用一次，所以有可能会和其他的两种能力发生冲突，而冲突的卡片数最多是B+C张，所以实际上对我们有用的卡片只是前面的A+B+C张。

#include 
    
     using namespace std;const int maxn = 500, INF = 1000000000;struct Edge{    int from, to, cap, flow, cost;};struct MCMF{    int n, m;    vector
     
       edges;    vector
      
        G[maxn];    bool 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 < n; i++) G[i].clear();        edges.clear();    }    void AddEdge(int from, int to, int cap, int cost)    {        edges.push_back((Edge)        {            from, to, cap, 0, cost        });        edges.push_back((Edge)        {            to, from, 0, 0, -cost        });        m = edges.size();        G[from].push_back(m-2);        G[to].push_back(m-1);    }    bool BellmanFord(int s, int t, int &flow, long long& cost)    {        memset(inq,0,sizeof(inq));        for(int i=0; i

Q; Q.push(s); while(!Q.empty()) { int u = Q.front(); Q.pop(); inq[u] = false; for(int i = 0; i < G[u].size(); i++) { Edge& e = edges[G[u][i]]; if(e.cap > 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] = true; } } } } if(d[t] == INF) return false; //s-t 不连通，失败退出 flow += a[t]; cost += (long long)d[t] * (long long)a[t]; int u = t; while(u != s) { edges[p[u]].flow += a[t]; edges[p[u]^1].flow -= a[t]; u = edges[p[u]].from; } return true; } pair

Mincost(int s, int t) { long long cost = 0; int flow = 0; while(BellmanFord(s, t, flow, cost)); return pair

{cost,flow}; }} sol;int a[100105],b[100105],c[100105],rk[100105];int id[310];bool cmpa(int i,int j){ if(a[i]==a[j])return a[i]+b[i]+c[i]>a[j]+b[j]+c[j]; return a[i]>a[j];}bool cmpb(int i,int j){ if(b[i]==b[j])return a[i]+b[i]+c[i]>a[j]+b[j]+c[j]; return b[i]>b[j];}bool cmpc(int i,int j){ if(c[i]==c[j])return a[i]+b[i]+c[i]>a[j]+b[j]+c[j]; return c[i]>c[j];}int main(){ // freopen("in.txt","r",stdin); int t; scanf("%d",&t); for(int i=0; i

转载于:https://www.cnblogs.com/TreeDream/p/7323683.html