Time Limit: 1000MS | Memory Limit: 10000K | |
Total Submissions: 7791 | Accepted: 3174 |
Description
As for a film,
- it will be made ONLY on some fixed days in a week, i.e., Alice can only work for the film on these days;
- Alice should work for it at least for specified number of days;
- the film MUST be finished before a prearranged deadline.
For example, assuming a film can be made only on Monday, Wednesday and Saturday; Alice should work for the film at least for 4 days; and it must be finished within 3 weeks. In this case she can work for the film on Monday of the first week, on Monday and Saturday of the second week, and on Monday of the third week.
Notice that on a single day Alice can work on at most ONE film.
Input
Output
Sample Input
2
2
0 1 0 1 0 1 0 9 3
0 1 1 1 0 0 0 6 4
2
0 1 0 1 0 1 0 9 4
0 1 1 1 0 0 0 6 2
Sample Output
Yes
No
Hint
A proper schedule for the first test case: 按时间点建边就好了
。。。1 - 7 写成 1 - 9 emm。。。
#include <iostream>
#include <cstdio>
#include <sstream>
#include <cstring>
#include <map>
#include <cctype>
#include <set>
#include <vector>
#include <stack>
#include <queue>
#include <algorithm>
#include <cmath>
#include <bitset>
#define rap(i, a, n) for(int i=a; i<=n; i++)
#define rep(i, a, n) for(int i=a; i<n; i++)
#define lap(i, a, n) for(int i=n; i>=a; i--)
#define lep(i, a, n) for(int i=n; i>a; i--)
#define rd(a) scanf("%d", &a)
#define rlld(a) scanf("%lld", &a)
#define rc(a) scanf("%c", &a)
#define rs(a) scanf("%s", a)
#define rb(a) scanf("%lf", &a)
#define rf(a) scanf("%f", &a)
#define pd(a) printf("%d\n", a)
#define plld(a) printf("%lld\n", a)
#define pc(a) printf("%c\n", a)
#define ps(a) printf("%s\n", a)
#define MOD 2018
#define LL long long
#define ULL unsigned long long
#define Pair pair<int, int>
#define mem(a, b) memset(a, b, sizeof(a))
#define _ ios_base::sync_with_stdio(0),cin.tie(0)
//freopen("1.txt", "r", stdin);
using namespace std;
const int maxn = 1e5 + , INF = 0x7fffffff;
int n, m, s, t;
int day[];
int head[maxn], cur[maxn], d[maxn], vis[maxn], nex[maxn << ], cnt; struct node
{
int u, v, c;
}Node[maxn << ]; void add_(int u, int v, int c)
{
Node[cnt].u = u;
Node[cnt].v = v;
Node[cnt].c = c;
nex[cnt] = head[u];
head[u] = cnt++;
} void add(int u, int v, int c)
{
add_(u, v, c);
add_(v, u, );
} bool bfs()
{
queue<int> Q;
mem(d, );
Q.push(s);
d[s] = ;
while(!Q.empty())
{
int u = Q.front(); Q.pop();
for(int i = head[u]; i != -; i = nex[i])
{
int v = Node[i].v;
if(!d[v] && Node[i].c > )
{
d[v] = d[u] + ;
Q.push(v);
if(v == t) return ;
}
}
}
return d[t] != ;
} int dfs(int u, int cap)
{
int ret = ;
if(u == t || cap == )
return cap;
for(int &i = cur[u]; i != -; i = nex[i])
{
int v = Node[i].v;
if(d[v] == d[u] + && Node[i].c > )
{
int V = dfs(v, min(cap, Node[i].c));
Node[i].c -= V;
Node[i ^ ].c += V;
ret += V;
cap -= V;
if(cap == ) break;
}
}
if(cap > ) d[u] = -;
return ret;
} int Dinic(int u)
{
int ans = ;
while(bfs())
{
memcpy(cur, head, sizeof(head));
ans += dfs(u, INF);
}
return ans;
} int main()
{
int T;
rd(T);
while(T--)
{
mem(head, -);
cnt = ;
rd(n);
s = , t = ;
int sum = ;
int w;
rap(i, , n)
{
rap(j, , )
{
rd(day[j]);
}
rap(j, , )
if(day[j] == )
rep(k, , day[])
add(i, n + k * + j, );
add(s, i, day[]);
// cout << day[8] << endl;
sum += day[];
}
rap(i, n + , )
add(i, t, );
if(sum == Dinic(s))
cout << "Yes" << endl;
else
cout << "No" << endl; } return ;
}
Time Limit: 1000MS | Memory Limit: 10000K | |
Total Submissions: 7791 | Accepted: 3174 |
Description
As for a film,
- it will be made ONLY on some fixed days in a week, i.e., Alice can only work for the film on these days;
- Alice should work for it at least for specified number of days;
- the film MUST be finished before a prearranged deadline.
For example, assuming a film can be made only on Monday, Wednesday and Saturday; Alice should work for the film at least for 4 days; and it must be finished within 3 weeks. In this case she can work for the film on Monday of the first week, on Monday and Saturday of the second week, and on Monday of the third week.
Notice that on a single day Alice can work on at most ONE film.
Input
Output
Sample Input
2
2
0 1 0 1 0 1 0 9 3
0 1 1 1 0 0 0 6 4
2
0 1 0 1 0 1 0 9 4
0 1 1 1 0 0 0 6 2
Sample Output
Yes
No
Hint
A proper schedule for the first test case: