栏目分类:
子分类:
返回
名师互学网用户登录
快速导航关闭
当前搜索
当前分类
子分类
实用工具
热门搜索
名师互学网 > IT > 面试经验 > 面试问答

poj 2906 Moving Pianos

面试问答 更新时间: 发布时间: IT归档 最新发布 模块sitemap 名妆网 法律咨询 聚返吧 英语巴士网 伯小乐 网商动力

poj 2906 Moving Pianos

#include<iostream>#include<cstring>#include<vector>#include<algorithm>#include<cmath>#include<cstdio>using namespace std;#define Max 0x1fffffff#define SIZE 200vector<pair<int, int> > jeo;struct edge{int from, to, val, next;}e[14000000];int v[SIZE], que[SIZE], dis[SIZE], cnt, cur[SIZE];void insert(int from, int to, int va){    e[cnt].from = from, e[cnt].to = to; e[cnt].val = va;    e[cnt].next = v[from];v[from] = cnt++;    e[cnt].from = to, e[cnt].to = from; e[cnt].val = 0;    e[cnt].next = v[to];v[to] = cnt++;}bool bfs(int n, int s, int t){    int head, tail, id;    head = tail = 0; que[tail++] = s;    memset(dis, -1, sizeof(int) * n);dis[s] = 0;    while(head < tail)         for(id = v[que[head++]]; id != -1; id = e[id].next) if (e[id].val > 0 && dis[e[id].to] == -1) {     dis[e[id].to] = dis[e[id].from] + 1;     que[tail++] = e[id].to;     if (e[id].to == t) return true; }    return false;}int Dinic(int n, int s, int t){    int maxflow = 0, tmp, i;    while(bfs(n, s, t))    {        int u = s, tail = 0;        for(i = 0; i < n; i++) cur[i] = v[i];        while(cur[s] != -1) if (u != t && cur[u] != -1 && e[cur[u]].val > 0 && dis[u] != -1 && dis[u] + 1 == dis[e[cur[u]].to]) {que[tail++] = cur[u]; u = e[cur[u]].to;} else if (u == t) {     for(tmp = Max, i = tail - 1; i >= 0; i--) tmp = min(tmp, e[que[i]].val);     for(maxflow += tmp, i = tail - 1; i >= 0; i--)     {         e[que[i]].val -= tmp;         e[que[i] ^ 1].val += tmp;         if (e[que[i]].val == 0) tail = i;     }     u = e[que[tail]].from; } else {     while(tail > 0 && u != s && cur[u] == -1) u = e[que[--tail]].from;     cur[u] = e[cur[u]].next; }    }    return maxflow;}int num[SIZE], ed[SIZE];int m, p, tt;bool build(int a, int b){    memset(v, -1, sizeof(v)); cnt = 0;    int s = 0, t = 101;    for(int i = 1; i <= 100; i++) if (i % 7 != a && i % 7 != b)        insert(s, i, p / 2);    memset(num, 0, sizeof(num)); memset(ed, 0, sizeof(ed));    for(int i = 0; i < m; i++)    {        num[jeo[i].second]++;        for(int j = jeo[i].first; j < jeo[i].second; j++) ed[j]++;    }    for(int i = 1; i <= 100; i++)        insert(i, t, num[i]), insert(i, i + 1, ed[i]);    return Dinic(t + 1, s, t) == m;}int main(){    scanf("%d", &tt);while(tt--)    {        scanf("%d%d", &m, &p);        jeo.clear();        for(int i = 0; i < m; i++)        {int a, b;scanf("%d%d", &a, &b); jeo.push_back(make_pair(a, b));        }        if (build(6, 0)) printf("finen");        else if (build(-1, -1)) printf("weekend workn");        else printf("serious troublen");    }         return 0;}
转载请注明:文章转载自 www.mshxw.com
本文地址:https://www.mshxw.com/it/370784.html
我们一直用心在做
关于我们 文章归档 网站地图 联系我们

版权所有 (c)2021-2022 MSHXW.COM

ICP备案号:晋ICP备2021003244-6号