下雪了

【Qt】窗口拖动代码

来自网上的博客,是通过鼠标相关的事件来实现的,封装起来很方便。

//Widget.h 
#ifndef WIDGET_H
#define WIDGET_H

#include <QWidget>

class QMouseEvent;
class Widget : public QWidget
{
    Q_OBJECT

public:
    Widget(QWidget *parent = 0);
    ~Widget();

protected:
    //拖拽窗口
    void mousePressEvent(QMouseEvent *event);
    void mouseMoveEvent(QMouseEvent *event);
    void mouseReleaseEvent(QMouseEvent *event);

private:
    bool        m_bDrag;
    QPoint      mouseStartPoint;
    QPoint      windowTopLeftPoint;
};

#endif // WIDGET_H
//Widget.cpp
#include <QMouseEvent>

Widget::Widget(QWidget *parent)
    : QWidget(parent)
    , m_bDrag(false)
{
    setWindowTitle("窗口拖拽移动");
    setFixedSize(640, 480);
}

Widget::~Widget()
{

}

/* QPoint QMouseEvent::pos() const
    Returns the position of the mouse cursor, relative to the widget that received the event.
    If you move the widget as a result of the mouse event, use the global position returned by globalPos() to avoid a shaking motion.
 */

//拖拽操作
void Widget::mousePressEvent(QMouseEvent *event)
{
    if(event->button() == Qt::LeftButton)
    {
        m_bDrag = true;
        //获得鼠标的初始位置
        mouseStartPoint = event->globalPos();
        //mouseStartPoint = event->pos();
        //获得窗口的初始位置
        windowTopLeftPoint = this->frameGeometry().topLeft();
    }
}

void Widget::mouseMoveEvent(QMouseEvent *event)
{
    if(m_bDrag)
    {
        //获得鼠标移动的距离
        QPoint distance = event->globalPos() - mouseStartPoint;
        //QPoint distance = event->pos() - mouseStartPoint;
        //改变窗口的位置
        this->move(windowTopLeftPoint + distance);
    }
}

void Widget::mouseReleaseEvent(QMouseEvent *event)
{
    if(event->button() == Qt::LeftButton)
    {
        m_bDrag = false;
    }
}

 

【Boost】发送/接收HTML请求(Get/Post)

头文件:

#include <boost/asio.hpp>
#include <boost/beast.hpp>
#include <boost/locale.hpp>

具体步骤:

void conn()
{

    try
    {
        //三个基础参数
        string host="zofz.cf";
        string port="80";
        string target="/123/";

        //http版本
        int version = 11;

        //建立基础IO接口,并初始化resolver和socket
        boost::asio::io_service io_se;
        boost::asio::ip::tcp::resolver resolver{ io_se };
        boost::asio::ip::tcp::socket socket{ io_se };

        //设定GET/POST请求
        boost::asio::streambuf request;
        std::ostream request_stream(&request);

        //创建http头,注意格式
        request_stream << "GET " << target << " HTTP/1.1 \r\n";
        request_stream << "Host: " << host << "\r\n";
        request_stream << "Accept: application/json \r\n";
        request_stream << "Accept-Encoding: gzip, deflate, br \r\n";
        request_stream << "Conection: keep-alive \r\n";
        request_stream << "Content-Type: application/x-www-form-urlencoded \r\n";
        request_stream << "User-Agent: " << ua << " \r\n";

        // 发送request
        write(socket, request);

        //声明一个容器来保存响应
        boost::beast::flat_buffer buf;
        response<string_body> resp;
        stringstream ss;

        //接收容器
        read(socket, buf, resp);
        
        //遍历Header
        for(auto &i:resp)
        {
            cout<<i.name()<<i.value()<<endl;
        }
        
        //输出body
        cout<<resp.body()<<endl;
    }
    catch (std::exception const& e)
    {
        //输出错误
        cout<< e.what()<<);
    }
}

 

【Boost】对JSON的操作

头文件:

#include <boost/property_tree/ptree.hpp>
#include <boost/property_tree/json_parser.hpp>

用法:

void encode()
{
    /*
    将形如:
    {
        "data":
        {
            "key":"value";
        }
    }
    的JSON文本转为string字符串
    */
    
    ptree root, data;
    stringstream ss;
    
    //创建data
    data.put("key", "value");
    
    //放入data
    root.put_child("data", data);
    
    //将JSON文本写入字符流
    write_json(ss, root);
    
    //读出字符串
    string json = ss.str();
}



void decode(string json)
{
    /*
    解析形如
    {
        "data":
        {
            "key":"value";
        }
    }
    的JSON文本到string中
    */
    ptree root, data;
    
    //将字符串读入字符流
    stringstream ss(json);
    
    //读出JSON格式的文本
    read_json(ss, root);
    
    //分离出data
    data = root.get_child("data");
    
    //分离出key,value
    string value = data.get & lt; string& gt; ("key");
}

 

洛谷P3386 【模板】二分图匹配

二分图匈牙利算法,归根结底就是递归找新边找找找!

#include<algorithm>
#include<iostream>
#include<cstdlib>
#include<cstring>
#include<string>
#include<vector>
#include<cstdio>
#include<stack>
#include<cmath>
#include<ctime>
#include<queue>
#include<deque>
#include<list>
#include<map>
#define int long long
#define ffor(i, a, b) for(ll i = a; i <= b; i++)
#define rfor(i, a, b) for(ll i = a; i >= b; i--)
#define mes(a,b) memset(a, b, sizeof(a))
#define cos(x) cos(x*PI/180.0)
#define sin(x) sin(x*PI/180.0)
#define stop system("pause")
#define see(s,x) cout<<(s)<<'='<<(x)<<endl
#define IMAX 0x7fffffff
#define PI 3.141592654
#define INF 0x3f3f3f3f
#define eps 1e-6
#define lowbit(x) (x&(-x))
#define test(x) cout<<"Test "<<(x)<<endl;
typedef long long ll;
ll mod;
ll max(ll a, ll b) { return(a > b) ? a : b; }
ll min(ll a, ll b) { return(a < b) ? a : b; }
using namespace std;

vector<int> G[1005];
int tab[1005];
bool v[1005];

bool deal(int x)
{
    for (int i : G[x])
    {
        if (!v[i])
        {
            v[i] = true;
            if (!tab[i] || deal(tab[i]))
            {
                tab[i] = x;
                return true;
            }
        }
    }
    return false;
}

signed main()
{
    mes(tab, 0);
    int n, m, e;
    cin >> n >> m >> e;
    ffor(i, 1, e)
    {
        int x, y;
        scanf("%lld%lld", &x, &y);
        if (x <= n && y <= m)
            G[x].push_back(y);
    }
    int res = 0;
    ffor(i, 1, n)
    {
        mes(v, 0);
        res += deal(i);
    }
    cout << res << endl;
}

洛谷 P3381 最小费用最大流(网络流/最小费用最大流/Dinic + SFPA)

如题,给出一个网络图,以及其源点和汇点,每条边已知其最大流量和单位流量费用,求出其网络最大流和在最大流情况下的最小费用。

输入格式

第一行包含四个正整数N、M、S、T,分别表示点的个数、有向边的个数、源点序号、汇点序号。

接下来M行每行包含四个正整数ui、vi、wi、fi,表示第i条有向边从ui出发,到达vi,边权为wi(即该边最大流量为wi),单位流量的费用为fi。

输出格式

一行,包含两个整数,依次为最大流量和在最大流量情况下的最小费用。

输入输出样例

输入 #1

4 5 4 3
4 2 30 2
4 3 20 3
2 3 20 1
2 1 30 9
1 3 40 5

输出 #1

50 280

说明/提示

时空限制:1000ms,128M

(BYX:最后两个点改成了1200ms)

数据规模:

对于30%的数据:N<=10,M<=10

对于70%的数据:N<=1000,M<=1000

对于100%的数据:N<=5000,M<=50000

样例说明:

如图,最优方案如下:

第一条流为4–>3,流量为20,费用为3*20=60。

第二条流为4–>2–>3,流量为20,费用为(2+1)*20=60。

第三条流为4–>2–>1–>3,流量为10,费用为(2+9+5)*10=160。

故最大流量为50,在此状况下最小费用为60+60+160=280。

故输出50 280。

思路:初学费用流,找到了一篇不错的教程,思路是利用最短路保证最小费用,再在最大流的基础上,算出最大流的最小的费用,似乎可以把sfpa换成dijkstra?

AC代码:

#include<algorithm>
#include<iostream>
#include<cstdlib>
#include<cstring>
#include<string>
#include<vector>
#include<cstdio>
#include<stack>
#include<cmath>
#include<ctime>
#include<queue>
#include<deque>
#include<list>
#include<map>
#define int long long
#define ffor(i, a, b) for(ll i = a; i <= b; i++)
#define rfor(i, a, b) for(ll i = a; i >= b; i--)
#define mes(a,b) memset(a, b, sizeof(a))
#define cos(x) cos(x*PI/180.0)
#define sin(x) sin(x*PI/180.0)
#define stop system("pause")
#define see(s,x) cout<<(s)<<'='<<(x)<<endl
#define IMAX 0x7fffffff
#define PI 3.141592654
#define INF 0x3f3f3f3f
#define eps 1e-6
#define lowbit(x) (x&(-x))
#define test(x) cout<<"Test "<<(x)<<endl;
typedef long long ll;
ll mod;
ll max(ll a, ll b) { return(a > b) ? a : b; }
ll min(ll a, ll b) { return(a < b) ? a : b; }
using namespace std;

struct unit
{
    int to;//指向
    int f;//流量
    int w;//单位花费
    int rev;//反向边序号
    unit() {};
    unit(int n, int ff, int ww, int r) :to(n), f(ff), w(ww), rev(r) {};
};
vector<unit> G[50001];
int cur[50001];
int dis[50001];
bool v[50001];

int n, m, st, ed;
int maxflow, mincost;

void add(int x, int y, int f, int w)//建边
{
    G[x].push_back(unit(y, f, w, G[y].size()));
    G[y].push_back(unit(x, 0, -w, G[x].size() - 1));//反向边,流量为0,单位花费为负
}

bool spfa()//标准SPFA
{
    ffor(i, 1, n)
    {
        v[i] = false;
        dis[i] = IMAX;
    }
    dis[st] = 0;
    queue<int> q;
    q.push(st);
    while (!q.empty())
    {
        int f = q.front();
        q.pop();
        v[f] = false;
        for (vector<unit>::iterator it = G[f].begin(); it != G[f].end(); it++)
        {
            unit u = *it;
            if (u.f && dis[f] + u.w < dis[u.to])
            {
                dis[u.to] = dis[f] + u.w;
                if (!v[u.to])
                {
                    q.push(u.to);
                    v[u.to] = true;
                }
            }
        }
    }
    return dis[ed] != IMAX;//能走到就返回
}

int dfs(int x, int f)
{
    if (x == ed)
        return f;
    v[x] = true;//防止重复走
    int sum = 0;
    for (int& i = cur[x]; i <= G[x].size() - 1; i++)
    {
        unit& u = G[x][i];
        if (!v[u.to] && u.f && dis[u.to] == dis[x] + u.w)
        {
            int flow = dfs(u.to, min(f - sum, u.f));
            if (flow)//确认可以流通,就对边进行操作,记录最大流和最小花费
            {
                sum += flow;
                u.f -= flow;
                G[u.to][u.rev].f += flow;
                mincost += u.w * flow;
                if (sum == f)break;
            }
        }
    }
    v[x] = false;
    return sum;
}
void dinic()
{
    while (spfa())
    {
        mes(cur, 0);
        maxflow += dfs(st, IMAX);
    }
}

signed main()
{
    cin >> n >> m >> st >> ed;
    maxflow = mincost = 0;
    ffor(i, 1, m)
    {
        int x, y, w, c;
        scanf("%lld%lld%lld%lld", &x, &y, &w, &c);
        add(x, y, w, c);
    }
    dinic();
    printf("%lld %lld\n", maxflow, mincost);
}