0分求助,不理解哪儿写出问题了
查看原帖
0分求助,不理解哪儿写出问题了
103604
ZHAKWF楼主2020/8/2 20:01
//#define LOCAL
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define mem(a, b) memset(a,b,sizeof(a))
#define INF 0x3f3f3f3f
#define DNF 0x7f7f7f7f
#define DBG printf("this is a input\n")
#define fi first
#define se second
#define mk(a, b) make_pair(a,b)
#define pb push_back
#define LF putchar('\n')
#define SP putchar(' ')
#define p_queue priority_queue
#define CLOSE ios::sync_with_stdio(0); cin.tie(0)

template<typename T>
void read(T &x) {x = 0;char ch = getchar();ll f = 1;while(!isdigit(ch)){if(ch == '-')f *= -1;ch = getchar();}while(isdigit(ch)){x = x * 10 + ch - 48; ch = getchar();}x *= f;}
template<typename T, typename... Args>
void read(T &first, Args& ... args) {read(first);read(args...);}
template<typename T>
void write(T arg) {T x = arg;if(x < 0) {putchar('-'); x =- x;}if(x > 9) {write(x / 10);}putchar(x % 10 + '0');}
template<typename T, typename ... Ts>
void write(T arg, Ts ... args) {write(arg);if(sizeof...(args) != 0) {putchar(' ');write(args ...);}}
using namespace std;

ll gcd(ll a, ll b) {
    return b == 0 ? a : gcd(b, a % b);
}

ll lcm(ll a, ll b) {
    return a / gcd(a, b) * b;
}
const int N = 100005;
int head[N] , cnt;
struct node{
    int f, t, next , w;
    double c;
}edge[1000005];
int n , m;
void add (int f, int t, int w, double co)
{
    edge[cnt].f = f;
    edge[cnt].c = co;
    edge[cnt].w = w;
    edge[cnt].t = t;
    edge[cnt].next = head[f];
    head[f] = cnt ++;
}
int s, t;
int mark[105][105];
double dis[N];
int fw[N], vis[N], pre[N];
queue <int> q;
bool spfa()
{
    for (int i = 0 ; i <= t ; i ++)
        dis[i] = -1.0;
    mem(fw,INF);
    mem(vis,0);
    pre[s] = pre[t] = -1;
    q.push(s);
    vis[s] = 1;
    dis[s] = 1.0;
    while(!q.empty())
    {
        int u = q.front();
        q.pop();
        vis[u] = 0;
        for (int i = head[u] ; i != -1 ; i = edge[i].next)
        {
            int v = edge[i].t;
            int w = edge[i].w;
            double c = edge[i].c;
            if(edge[i].w && dis[u] * c > dis[v])
            {
                dis[v] = dis[u] * c;
                fw[v] = min(fw[v], w);
                pre[v] = i;
                if(vis[v] == 0)
                {
                    q.push(v);
                    vis[v] = 1;
                }
            }
        }
    }
    return pre[t] != -1;
}
void FYL()
{
    while(spfa())
    {
        for (int i = pre[t] ; i != -1 ; i = pre[edge[i].f])
        {
            edge[i].w -= fw[t];
            edge[i^1].w += fw[t];
        }
    }
    return ;
}

int main()
{
    mem(head, -1) , cnt = 0;
    read (n, m);
    s = 0 , t = n + m + 1;
    for (int i = 1; i <= n ; i ++)
        for (int j = 1 ; j <= m ; j ++)
        {
            int x;
            read(x);
            double xx = 0.01 * x;
            add(i, n + j, 1, xx);
            add(n + j, i, 0, 1.0 / xx);
        }
    for (int i = 1 ; i <= n ; i ++)
    {
        int x;
        read (x);
        add(s, i, x , 1.0);
        add (i , s , 0 , 1.0);
    }
    for (int i = 1 ; i <= m ; i ++)
    {
        int x;
        read (x);
        add(i + n, t, x , 1.0);
        add (t , i + n , 0 , 1.0);
    }
    FYL();
    for (int i = 0 ; i < cnt ; i ++)
    {
        if(!edge[i].w)
            mark[edge[i].f][edge[i].t-n] = 1;
    }
    for (int i = 1; i <= n ; i ++)
    {
        for (int j = 1; j <= m ; j ++)
            write(mark[i][j]);
        LF;
    }
}
2020/8/2 20:01
加载中...