beloved_ACM

     摘要: 最大点权独立集的问题。不解释。 #include <iostream>#include <queue>using namespace std;const int MAXN = 2000;const int INF = 0x3fffffff;int&nbs...  阅读全文

Stock Chase

Time Limit: 5000ms, Special Time Limit:12500ms, Memory Limit:65536KB

Total submit users: 28, Accepted users: 20

Problem 11785 : No special judgement

Problem description

I have to admit, the solution I proposed last year for solving the bank cash crisis didn’t solve the whole economic crisis. As it turns out, companies don’t have that much cash in the first place. They have assets which are primarily shares in other companies. It is common, and acceptable, for one company to own shares in another. What complicates the issue is for two companies to own shares in each other at the same time. If you think of it for a moment, this means that each company now (indirectly) controls its own shares. New market regulation is being implemented: No company can control shares in itself, whether directly or indirectly. The Stock Market Authority is looking for a computerized solution that will help it detect any buying activity that will result in a company controlling its own shares. It is obvious why they need a program to do so, just imagine the situation where company A buying shares in B, B buying in C, and then C buying in A. While the first two purchases are acceptable. The third purchase should be rejected since it will lead to the three companies controlling shares in themselves. The program will be given all purchasing transactions in chronological order. The program should reject any transaction that could lead to one company controlling its own shares. All other transactions are accepted.

Input

Your program will be tested on one or more test cases. Each test case is specified on T + 1 lines. The first line specifies two positive numbers: (0 < N ≤ 234) is the number of companies and (0 < T ≤ 100, 000) is the number of transactions. T lines follow, each describing a buying transaction. Each transaction is specified using two numbers A and B where (0 < A,B ≤ N) indicating that company A wants to buy shares in company B. The last line of the input file has two zeros.

Output

For each test case, print the following line: k. R Where k is the test case number (starting at one,) R is the number of transactions that should be rejected.

Sample Input

3 6 1 2 1 3 3 1 2 1 1 2 2 3 0 0

Sample Output

1. 2

解题报告:开始想得太复杂了,这道题有点像上次天津网络赛那个最短路,类似于floyd那样做的,那是点,这是边,每次添加一条边,让后去判断是否有环,有环就不添加,并且计数加1

求最大匹配，不解释。

kruscal，水过。
官方做法是用dijkstra把松弛操作改成 d[j] = d[j]<min(d[i],graph[i][j])?min(d[i],graph[i][j]):d[j]; 其中d[i]代表的就是求从1到i路径中最小边的最大值。

     摘要: 实际上就是求最大权闭合图，还是比较容易的，没OJ交，就过了下样例。 #include <iostream>#include <queue>using namespace std;const int MAXN = 500;const int INF = 0...  阅读全文

这道题目读起来难度挺大，主要还是建模，模型还是不难。下面复制下别人的解题报告，代码是自己的。

【题目大意】

针对输入数据来说题目意思吧。
7 2 （N个房间，要保护2号房间）
NI 0 {0号房间，NI代表没有入侵者}
I 3 0 4 5 {1号房间，I代表该房间内有入侵者，该房间有3个门，分别连向0，4，5号房间，且控制端在1号房间}
NI 2 1 6
NI 2 1 2
NI 0
NI 0
NI 0
门一开始都是可以打开的，若要关闭或再次打开某扇门必须在控制端进行。
问使得所有入侵者不进入要保护的房间最少需要关闭几扇门，如果入侵者必然会进入要保护的房间则输出PANIC ROOM BREACH

【解题思路】

把要保护的房间作为汇点，设为T，新增源点S。
对于有入侵者的房间I，连一条从S向I容量为inf的弧。
对于每扇门连接的（I,J），若控制端在I，则从I向J连一条容量为Max的弧，从J向I连一条容量为1的弧。
这样，想使得S和T不连通，图中的最小割就对应了一种最小的关门方案，如果割中存在容量为inf的弧，显然是无解的。

  这题不能用邻接矩阵，因为有重边，但是费用或流量又不一样。做法是拆边，假设一条边的容量为ci，把每条边拆成ci条容量为1的边，取费用为1*a ,3*a,5*a 依次类推。

#include <iostream>
using namespace std;

#include <iostream>
#include <queue>
using namespace std;

const int INF = 0x7fffffff;
const int MAXN = 10001;

struct node {
   int v;int next;
   int flow;int cap;
   int cost;
}space[4*MAXN];

int sps;
int k,u,v,ci,aa;
int edge[MAXN];
int c,f;
int first[MAXN];
int n,m;
int p[MAXN];

void addedge(int head[],int u,int v,int cap,int cost) {
  

   space[sps].v = v;
   space[sps].cap = cap;
   space[sps].cost = cost;
   space[sps].next = head[u];
   space[sps].flow = 0;
   head[u] = sps++;
  
   space[sps].v = u;
   space[sps].cap = 0;
   space[sps].cost = -cost;
   space[sps].next = head[v];
   space[sps].flow = 0;
   head[v] = sps++;
  
}

void solve() {
   queue<int> q;
   int d[MAXN];
   c = f = 0;
   int s = 1,t = n;
   for(;f < k;) {
      bool inq[MAXN];
      for(int i = 0; i <= n+1; i++) d[i] = (i == s? 0 : INF);
      memset(inq,0,sizeof(inq));
      q.push(s);
      while(!q.empty()) {
         int u = q.front();
         q.pop();
         inq[u] = false;
         for(int addr = first[u]; addr != -1; addr = space[addr].next) {
            int v = space[addr].v;
            if(space[addr].cap > space[addr].flow && d[v] > d[u] + space[addr].cost ) {
               p[v]= u;
               edge[v] = addr; //记录增广路u to v的编号。
               d[v] = d[u] + space[addr].cost;
               if(!inq[v]) {
                  inq[v] = true;
                  q.push(v);
               }
            }
         }
      }
     
     
         if(d[t] == INF) break;
         int a =INF;
         for(int u = t; u!= s; u = p[u]) a = min(a,space[edge[u]].cap - space[edge[u]].flow);
        
         for(int u = t; u != s; u = p[u]) {
            space[edge[u]].flow += a;
            space[edge[u]^1].flow -= a; //异或奇数边减-1偶数边加1，妙
         }
        
         c+= d[t] *a;
         f += a;
   }
}

int main() {
   
   while(scanf("%d%d%d",&n,&m,&k)!=EOF) {
      sps = 0;
      memset(first,-1,sizeof(first));
      for(int i = 0; i < m; i++) {
         int num = 1;
         scanf("%d%d%d%d",&u,&v,&aa,&ci);
         for(int j = 0; j < ci; j++) {
            addedge(first,u,v,1,aa*num);
            num += 2;
         }
      }
  

 //     addedge(first,0,1,INF,0);
  //    addedge(first,n,n+1,INF,0);
    solve();  
   if(f == k)
      printf("%d\n",c);
   else
      printf("-1\n");
}
   return 0;
}

 

  题目中的要求是求路上最长的一部分中的边最短。每条边只能经过一次，FJ要去T次。每次都是找最短路径，先得排序，可以用参数搜索，所谓参数搜索就去用一个量去尝试，最大流做为判定，然后寻找最优值。

#include <iostream>
#include <algorithm>
#include <queue>
using namespace std;

const int INF = 0x7fffffff;
const int EMAXN = 40001;
const int VMAXN = 201;
int c[VMAXN][VMAXN];
int d[VMAXN];
int s,t;
int vex;
int num[VMAXN],pre[VMAXN];
int n,m,g,u,v,w;
struct node {
  int u,v,w;
}edge[EMAXN];

bool cmp(node a,node b) {
   return a.w < b.w;
}

void ini_d(int n,int s,int t) //BFS计算标号，汇点t标号为0
{
    int k;
    queue<int>Q;
   memset(d,1,sizeof(d));
    memset(num,0,sizeof(num));
    Q.push(t);
    d[t]=0;
    num[0]=1;
    while (!Q.empty())
    {
        k=Q.front(),Q.pop();
        for (int i=0;i<vex+1;i++)
        {
            if (d[i]>=vex+1&&c[i][k]>0)
            { d[i]=d[k]+1;
                Q.push(i);
                num[d[i]]++;
            }
        }
    }
}
int findAlowArc(int i)       //从i出发寻找允许弧
{
    int j;
    for (j=0;j<vex+1;j++) if (c[i][j]>0&&d[i]==d[j]+1) return j;

    return -1;
}

int reLable(int i)         //重新标号
{
    int mm=INT_MAX;
    for (int j=0;j<vex+1;j++)
        if (c[i][j]>0) mm=min(mm,d[j]+1);

    return mm==INT_MAX?m:mm;
}

int maxFlow(int vex,int s,int t)      //从源点s出发的最大流
{   
     ini_d(vex,s,t);
    int flow=0,i=s,j;
    int delta;              //增量

    memset(pre,-1,sizeof(pre));
    while (d[s]<vex+1)
    {
        j=findAlowArc(i);
        if (j>=0)
        {
            pre[j]=i;
            i=j;
            if (i==t)           //更新残留网络
            {
                delta=INT_MAX;
                for (i=t;i!=s;i=pre[i]) delta=min(delta,c[pre[i]][i]);
                for (i=t;i!=s;i=pre[i]) c[pre[i]][i] -= delta, c[i][pre[i]] += delta;
                flow += delta;
            }
        }
        else
        {
            int x=reLable(i);       //重新标号
            num[x]++;
            num[d[i]]--;
            if (num[d[i]]==0) return flow;      //间隙优化
            d[i]=x;
            if (i!=s) i=pre[i];
        }
    }
    return flow;
}


bool solve(int x) {
  
   memset(c,0,sizeof(c));
   for(int i = 0; i <= x;i++) {
      c[edge[i].u][edge[i].v]++;
      c[edge[i].v][edge[i].u]++;
   }
  
       
  
   int temp = maxFlow(vex,s,t);
  // cout<<temp<<endl;
   if(temp >= g) return true;
   else return false;
}

int main() {
  
   while(scanf("%d%d%d",&n,&m,&g) != EOF) {
      for(int i = 0; i < m; i++) {
         scanf("%d%d%d",&u,&v,&w);
         edge[i].u = u;
         edge[i].v = v;
         edge[i].w = w;
      }
     
      sort(edge,edge+m,cmp);
     
      s = 1,t = n;
      vex = n;
      int l  = 0, r = m,mid;
      while(l < r) {
         mid = (l + r)/2;
         if(solve(mid))
            r = mid;
         else
            l = mid + 1;
      }
     
      printf("%d\n",edge[r].w);
   }
  // system("pause");
   return 0;
}

     摘要:    建模很简单，设置源点连接正权点，边权为该点值，负权点连接汇点，边权点为该点的绝对值，输入的边权值设为INF，然后求最大流，然后让正权点值的累加和减去最大流就是闭合图的最大权。《最小割模型在信息学竞赛中的应用》有详细的证明。 #include <iostream>using namespace std;const int...  阅读全文