首页 > 代码库 > Virtual Barber of the Army of Mages

Virtual Barber of the Army of Mages

2024-07-02 15:24:36   219人阅读

http://acm.hust.edu.cn/vjudge/contest/view.action?cid=45301#problem/A

题意：有n个人，k个理发师一。每个人需要理两次头发。每人有到达时间和他们等待的最大时间。求每个人能不能在他们等待的最长时间之前理完发。如果能，输出他理发的时刻。

题解：最大流……n个人和时刻连容量为1的边，源点和人之间为容量为2的边，时刻和汇点之间为容量为k的边。

注意：时刻与人建边的时候要注意是在时间段内，要减去min。输出理发时刻时应该+min。

建图还是不熟啊……怒wa了一天……唉……

  1 #include <iostream>
  2 #include <cstring>
  3 #include <cstdio>
  4 #include <cstdlib>
  5 #include <cmath>
  6 #include <string>
  7 #include <vector>
  8 #include <list>
  9 #include <map>
 10 #include <queue>
 11 #include <stack>
 12 #include <bitset>
 13 #include <algorithm>
 14 #include <numeric>
 15 #include <functional>
 16 #include <set>
 17 #include <fstream>
 18 
 19 using namespace std;
 20 
 21 const int maxn=1010;
 22 const int INF=1<<28;
 23 struct edge{
 24     int to,cap,rev;
 25 };
 26 vector<edge> G[maxn*maxn];
 27 int level[maxn*maxn];
 28 int iter[maxn*maxn];
 29 int ti[maxn*maxn][2];
 30 void add_edge(int from,int to,int cap)
 31 {
 32     G[from].push_back((edge{to,cap,(int)G[to].size()}));
 33     G[to].push_back((edge{from,0,(int)G[from].size()-1}));
 34 }
 35 
 36 void bfs(int s)
 37 {
 38     memset(level, -1, sizeof(level));
 39     queue<int> que;
 40     level[s]=0;
 41     que.push(s);
 42     while (!que.empty()) {
 43         int v=que.front();
 44         que.pop();
 45         for (int i=0; i<G[v].size(); i++) {
 46             edge &e=G[v][i];
 47             if (e.cap>0&&level[e.to]<0) {
 48                 level[e.to]=level[v]+1;
 49                 que.push(e.to);

 50             }
 51         }
 52     }
 53 }
 54 
 55 int dfs(int v,int t,int f)
 56 {
 57     if (v==t) {
 58         return f;
 59     }
 60     for (int &i=iter[v]; i<G[v].size(); i++) {
 61         edge &e=G[v][i];
 62         if (e.cap>0&&level[v]<level[e.to]) {
 63             int d=dfs(e.to,t,min(f,e.cap));
 64             if (d>0) {
 65                 e.cap-=d;
 66                 G[e.to][e.rev].cap+=d;
 67                 return d;
 68             }
 69         }
 70     }
 71     return 0;
 72 }
 73 
 74 int max_flow(int s,int t)
 75 {
 76     int flow=0;
 77     for (; ; ) {
 78         bfs(s);
 79         if (level[t]<0) {
 80             return flow;
 81         }
 82         memset(iter, 0, sizeof(iter));
 83         int f;
 84         while ((f=dfs(s, t, INF))>0) {
 85             flow+=f;
 86         }
 87     }
 88 }
 89 
 90 int n,k;
 91 
 92 int main()
 93 {
 94    // freopen("/Users/apple/Desktop/A/A/in", "r", stdin);
 95    // freopen("/Users/apple/Desktop/A/A/out", "w", stdout);
 96     while ((scanf("%d%d",&n,&k))!=EOF) {
 97         for (int i= 0; i < maxn; i++)
 98             G[i].clear();
 99         memset(ti, 0, sizeof(ti));
100         int min1=1000000;
101         int max1=-1;
102         int maxtime=-1;
103         for (int i=0; i<n; i++) {
104             scanf("%d%d",&ti[i][0],&ti[i][1]);
105             if (ti[i][0]<min1) {
106                 min1=ti[i][0];
107             }
108             if (ti[i][0]+ti[i][1]-1>max1) {
109                 max1=ti[i][0]+ti[i][1]-1;
110             }
111         }
112         //cout<<min1<<" "<<max1<<endl;
113         //min1--;
114         int time1=max1-min1+1;
115         int s=n+time1;
116         int t=s+1;
117        // s到人 0~n-1
118         for (int i=0; i<n; i++) {
119             add_edge(s, i, 2);
120          //   printf("i: s %d n %d\n",s,i);
121         }
122         //cout<<"22222222"<<endl;
123         //时刻到t n~n+time1-1
124         for (int i=0; i<time1; i++) {
125             add_edge(n+i, t, k);
126           //  printf("i: time %d t %d\n",n+i,t);
127         }
128         //cout<<"1111111"<<endl;
129         //人到时刻 
130         for (int i=0; i<n; i++) {
131             for (int j=ti[i][0]; j<ti[i][1]+ti[i][0]; j++) {
132                 add_edge(i, n+j-min1, 1);
133           //      printf("i: n %d time %d\n",i,n+j-min1);
134             }
135         }
136         if (max_flow(s, t)==2*n) {
137             printf("Yes\n");
138             for (int i=0; i<n; i++) {
139                 int cnt=1;
140                 for (int j=0; j<G[i].size(); j++) {
141                     if (G[i][j].cap==0&&G[i][j].to>=n&&G[i][j].to<=n+time1-1) {
142                         int res=G[i][j].to-n+min1;
143                         printf("%d%s",res,cnt!=2?" ":"\n");
144                         cnt++;
145                     }
146                     if (cnt==3) {
147                         break;
148                     }
149                 }
150             }
151         }
152         else printf("No\n");
153     }
154     return 0;
155 }

 


联系
我们